CF1917C

FiraCode · 2023-12-25 18:21:46 · 题解

思路:

首先假如数组开始全为 0 怎么做。

那么显然是每进行一次操作 1，就立马进行操作 2。因为若再进行一次，那么相等的贡献最多不变，因为是对前缀加，第一次是 1 满足，而第二次只有 2 满足或者没有，后面同理。

然后看不全为 0 怎么做。

我们发现 n 比较小，考虑暴力做 2n 轮，然后对于每一轮都计算贡献。也就是对于 i(0 \le i \le 2n) 来说，我们就是求做 i 的贡献加上剩余轮数按照刚才的策略的贡献。

而为什么做 2n 轮？是因为当执行 2n 轮时，你可以直接按照上述 2 轮一个贡献，就可以到 n 的贡献，而若一直执行的话，最多也就所有的数字都一样，最多也就是 n，所以没必要在往后枚举了。

当然做的轮数还要 <d。

时间复杂度 \mathcal{O(Tn^2)}。

Code:

#include <bits/stdc++.h>

using namespace std;

int T;
int n, k, d;
int a[2010], v[100010];
int cnt[4010];

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &k, &d);
        cnt[0] = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), cnt[0] += a[i] == i;
        for (int i = 1; i <= k; ++i) scanf("%d", &v[i]);
        for (int i = 1; i <= 2 * n && i < d; ++i) {
            cnt[i] = 0;
            for (int j = 1; j <= v[(i - 1) % k + 1]; ++j) a[j]++;
            for (int j = 1; j <= n; ++j) cnt[i] += a[j] == j;
        }
        int ans = 0;
        for (int i = 0; i <= 2 * n && i < d; ++i) {
            // cout << cnt[i] << endl;
            ans = max(ans, cnt[i] + (d - i - 1) / 2);
        }
        printf("%d\n", ans);
    }
    return 0;
}