题解：CF1969C Minimizing the Sum

Rex01 · 2025-03-14 16:35:42 · 题解

CF1969C 题目传送门

题目大意

有一个长度为 n 的整数数组 a。总共可以执行 k 次操作：选择数组中的一个元素并将其替换为任意一个相邻元素的值。你的任务是计算执行 k 次操作后，数组的最小可能总和是多少。

解决思路

首先来看一个例子：例如，如果 a=[3,1,2]，你可以通过一次操作得到数组 [3,3,2]，[3,2,2] 和 [1,1,2] 中的一个，但不能得到 [2,1,2] 或 [3,4,2]。

接下来很容易想到区间 dp。

求解:对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

我们定义 ans_{i, j}：前 i 个元素经过 j 次操作后得到的最小的和。再定义 val_{i, j}：前 i 个元素开始连续 j 个元素经过 j 次操作后最小的和。然后我们可以得到如下状态转移方程：

最终得到的 min_{i \le k}\ \ ans_{i, j} 即为所求答案。

预处理 val_{i, j} 和动态规划求解 ans_{i, j} 的时间复杂度都为 O(nk ^ 2)，预处理的过程可以优化成 O(nk)，总时间复杂度 O(nk ^ 2)，可以通过。

代码展示

这段代码通过动态规划的方法，计算在最多进行 k 次操作后，数组的最小和。p_{i, j} 用于存储从位置 i 开始，进行 j 次操作后可以得到的最小值，而 ans_{i, j} 用于存储前 i 个元素进行最多 j 次操作后的最小和。

#include<iostream>
#define ll long long
using namespace std;

const int N=3e5+10;
ll T,n,k,a[N],p[N][15],ans[N][15];

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            p[i][0]=a[i];
        }
        for(int j=1;j<=k;j++)
            for(int i=1;i+j<=n;i++)
                p[i][j]=min(p[i][j-1],(ll)a[i+j]);
        for(int j=1;j<=k;j++)
            for(int i=1;i+j<=n;i++)
                p[i][j]*=(j+1);
        for(int i=1;i<=n;i++)
        {
            ans[i][0]=ans[i-1][0]+a[i];
            for(int j=1;j<=k;j++)
            {
                ans[i][j]=min(ans[i-1][j]+a[i],ans[i][j-1]);
                for(int h=0;h<i&&h<=j;h++)
                    ans[i][j]=min(ans[i][j],ans[i-h-1][j-h]+p[i-h][h]);
            }
        }
        cout<<ans[n][k]<<endl;
    }
    return 0;
}