小猴编程------彩色蜡烛

这道题第一眼一定是暴力枚举，像这样：

bool vis[N];
int maxn = -1;
for (int i = k; i <= n; i++) {
    int cnt = 0;
    memset(vis, 0, sizeof vis);
    for (int j = 1; j <= i - k + 1; j++) {
        if (!vis[a[j]]) vis[a[j]] = 1, cnt++;
    }
    maxn = max(maxn, cnt);
}
cout << maxn;

这样做时间复杂度为 $O(n^2)$，经测试35分

仔细想想正解
正解其实是DP，仔细分析发现：

• 从x+1开始的连续蜡烛=从x开始的连续蜡烛去掉a[x]再加上a[x + k - 1];

所以转移即可

然后就

AC了
本人蒟蒻，如有更简单的做法私信我