题解：CF1969C Minimizing the Sum

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

次操作后最小的和。然后我们可以得到如下状态转移方程：

ans_{i, j} = \begin{cases} 0 & i = 0; \\ \min_{h\le \min(i - 1, j)}(ans_{i - h - 1, j - h} + val_{i - h, h}) & i > 0. \end{cases}

最终得到的

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

次操作后的最小和。

CPP

#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;
}

题解：CF1969C Minimizing the Sum

文章操作

CF1969C 题目传送门

题目大意

解决思路

代码展示

相关推荐

评论

题解：CF1969C Minimizing the Sum