CF1862G The Great Equalizer

题目链接

先不考虑修改操作。

直接模拟题目意思，可以发现最后留下的一定是最小的数字（因为相同的数每次会保留第一个）。我当时是顺着这个思路做的题目，现在想想反过来想好像会让问题变得更简单，即认为每次保留最后一个相同的数字。

那么现在每次留下的就是最后一个数字，显然每次操作会让这个数字加一，只需要考虑一共需要多少次操作能把数字消到只剩一个即可。

根据题目意思，相邻两个数之间每次操作后差的绝对值会减少一，也就是经过两数差次数后会消掉一个，所以操作次数即为相邻两数差的最大值（排序后）。一次询问的答案也就是最大值+相邻两数差的最大值。

结合修改操作，只需要两个 \(multiset\) 维护即可，感觉代码细节还是不少的。

#include<bits/stdc++.h>

using namespace std;

const int N = 3000;
int n, k, a[N + 9], f[N + 9][N + 9], g[N + 9][N + 9], ans[N + 9], sum1[N + 9], sum0[N + 9];
string s;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d", &n, &k);
        cin >> s;
        for (int i = 1; i <= n; i++)
            a[i] = s[i - 1] - '0';
        for (int i = 0; i <= n + 1; i++)
            for (int j = 0; j <= k; j++)
                f[i][j] =  g[i][j] = 0;
        for (int i = 0; i <= n + 1; i++)
            sum0[i] = sum1[i] = 0, ans[i] = -(1 << 30);
        for (int i = 1; i <= n; i++)
        {
            sum0[i] = sum0[i - 1] + (a[i] == 0);
            sum1[i] = sum1[i - 1] + (a[i] == 1);
        }
        a[n + 1] = a[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            int l = 0;
            for (int j = i; j <= n + 1; j++)
                if (a[j] == 0) f[i][l] = j - i, l++;
            while (l <= k) f[i][l] = n - i + 1, l++;
        }
        for (int i = 1; i <= n; i++)
        {
            int l = 0;
            for (int j = i; j >= 0; j--)
                if (a[j] == 0) g[i][l] = i - j, l++;
            while (l <= k) g[i][l] = i, l++;
        }
        for (int j = 0; j <= k; j++)
            for (int i = 1; i <= n; i++)
                g[i][j] = max(g[i][j], g[i - 1][j]);
        for (int j = 0; j <= k; j++)
            for (int i = n; i >= 1; i--)
                f[i][j] = max(f[i][j], f[i + 1][j]);
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++)
            {
                int l = j - i + 1;
                int K = sum1[j] - sum1[i - 1];
                K = k - K;
                if (K >= 0)
                    ans[l] = max(ans[l], max(f[j + 1][K], g[i - 1][K]));
            }
        ans[0] = f[1][k];
        /*puts("ans");
        for (int i = 0; i <= n; i++)
            printf("%d ", ans[i]);
        puts("");*/
        for (int i = 1; i <= n; i++)
        {
            int tmp = 0;
            for (int j = 0; j <= n; j++)
                tmp = max(tmp, i * j + ans[j]);
            printf("%d ", tmp);
        }
        puts("");
    }
    return 0;
}