题解：CF1969C Minimizing the Sum

· · 题解

首先，每次操作的时候一定是用小的来替换大的，这时数组总和会减少一个值（就是这两个数的差）。

设 f_{i,j} 表示前 i 个元素执行 j 次操作后可以减去的最大值，最后的答案就是 sum_n - f_{n,k}。

每次操作可以将一段连续子串替换为其中的最小值。设操作次数为 l，则可以这样处理长度为 (l+1) 的一段区间。所消去的值为区间总和减去 (l+1) 乘区间最小值，即：

\sum_{j=i-l}^{i} a_j - \min_{j=i-l}^{i} a_j

（上面的 i 表示区间右端点）

枚举操作次数 i 和 数列末尾 j，通过枚举操作次数 l ，就可以用上面的式子就可以求出所有 f_{j,i} 的值。

f_{j,i} = \max\left\{ f_{j-l-1,i-l} + sum\{a_{j-l} \sim a_{j}\} - \min\{a_{j-l} \sim a_j\} \times (l+1) \right\}

上面的式子中，等号右边表示：当后面连续操作 l 次时得到可消去的最大值，等于前 (j-l-1) 个数执行 (i-l) 次操作所能消去的最大值，加上将后面的 (l+1) 个数合并替换为区间最小值所能消去的值。

注意操作次数 i 需要从 0 开始枚举，枚举 l 的时候需要排除负数下标（排除不可能的情况）。

时间复杂度 O(nk^2)，在数据范围是 1 \le n \le 3 \times 10^5,0 \le k \le 10 的情况下可以接受（实际上只需 359 ms 即可）。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=3e5+5,K=15;
int n,k,a[N];
long long sum[N],f[N][K];
long long getsum(int l,int r){return sum[r]-sum[l-1];}

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
        }
        for(int i=0;i<=k;i++)
            for(int j=1;j<=n;j++)
            {
                long long mina=a[j];
                for(int l=1;j-l>=1&&i-l>=0;l++) //l operations: [j-l,j](len=l+1)
                {
                    mina=min(mina,(long long)a[j-l]);
                    f[j][i]=max(f[j][i],f[j-l-1][i-l]+getsum(j-l,j)-mina*(l+1));
                }
                f[j][i]=max(f[j-1][i],f[j][i]);
            }
        printf("%lld\n",sum[n]-f[n][k]);

        for(int i=0;i<=k;i++)
            for(int j=1;j<=n;j++)
                f[j][i]=0;
        for(int i=1;i<=n;i++)
            a[i]=sum[i]=0;
    }
    return 0;
}