首页 > 代码库 > [codevs1048]石子归并&&[codevs2102][洛谷P1880]石子归并加强版

[codevs1048]石子归并&&[codevs2102][洛谷P1880]石子归并加强版

2024-11-17 10:24:02   203人阅读

codevs1048：

题目大意：有n堆石子排成一列，每次可合并相邻两堆，代价为两堆的重量之和，求把他们合并成一堆的最小代价。

解题思路：经典区间dp。设$f[i][j]$表示合并i~j的石子需要的最小代价。则有$f[i][j]=min(f[i][k]+f[k+1][j]+\sum\limits _{l=i}^{j}a[l])$，时间复杂度$O(n^3)$。

C++ Code：

#include<cstdio>#include<cstring>using namespace std;int n,a[102],f[102][102],s[102];int main(){	scanf("%d",&n);	memset(f,0x3f,sizeof f);	for(int i=1;i<=n;++i)scanf("%d",&a[i]),s[i]=s[i-1]+a[i],f[i][i]=0;	for(int i=n;i;--i)	for(int j=i+1;j<=n;++j)	for(int k=i;k<j;++k)	if(f[i][j]>f[i][k]+f[k+1][j]+s[j]-s[i-1])f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1];	printf("%d\n",f[1][n]);	return 0;}

 注意代码第9行，为什么i要倒着循环？举个栗子，如果要求f[1][10]，就有f[1][10]=min(f[1][10],f[1][5]+f[6][10]+sum[1][10])，但是i才循环到1，就需要f[6][10]的结果，于是导致答案错误。而倒着循环，就可保证i+1~n的所有数据都已求完，就不会导致答案错误了。

 

 

codevs2102&&洛谷P1880：

题目大意：有n堆石子摆成环状，每次可合并相邻两堆，代价为两堆的重量之和，求把他们合并成一堆的最小代价和最大代价。

解题思路：本题除了是个环以外，和上题没什么区别。我们可以用化环为链的方法，具体的实现就是将这个环的单圈复制一遍，然后做n次上述dp即可。求最大价值就是把状态转移方程里的$min$改成$max$即可。时间复杂度$O(n^4)$，但代码运行量应该是不到这个极限的。

C++ Code：

 

#include<cstdio>#include<cstring>using namespace std;int n,a[202],fmax[202][202],fmin[202][202],s[202],Max=0,Min=200000000;void dp(int h){	for(int i=n;i;--i){		fmax[i+h][i+h]=fmin[i+h][i+h]=0;		for(int j=i+1;j<=n;++j){			fmax[i+h][j+h]=0;			fmin[i+h][j+h]=200000000;			for(int k=i;k<j;++k){				if(fmax[i+h][j+h]<fmax[i+h][k+h]+fmax[k+h+1][j+h]+s[j+h]-s[i+h-1])				fmax[i+h][j+h]=fmax[i+h][k+h]+fmax[k+h+1][j+h]+s[j+h]-s[i+h-1];				if(fmin[i+h][j+h]>fmin[i+h][k+h]+fmin[k+h+1][j+h]+s[j+h]-s[i+h-1])				fmin[i+h][j+h]=fmin[i+h][k+h]+fmin[k+h+1][j+h]+s[j+h]-s[i+h-1];			}		}	}	if(Max<fmax[1+h][n+h])Max=fmax[1+h][n+h];	if(Min>fmin[1+h][n+h])Min=fmin[1+h][n+h];}int main(){	scanf("%d",&n);	for(int i=1;i<=n;++i)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];	for(int i=n+1;i<2*n;++i)	a[i]=a[i-n],s[i]=s[i-1]+a[i];	for(int i=1;i<=n;++i)	dp(i-1);	printf("%d\n%d\n",Min,Max);	return 0;}

 

[codevs1048]石子归并&&[codevs2102][洛谷P1880]石子归并加强版


联系
我们