石子合并

https://loj.ac/problem/10147

题目描述

  有(n)堆石子围成一圈，每次可以将相邻两堆合并为一堆，合并的得分为合并成的石子的数量，求合并的最大得分和最小的得分。

思路

  首先显然我们要化环为链，接下来考虑如果进行类似合并果子贪心的选择，那么可以构造出反例，而且数据比较小，我们考虑(dp)，用(f[i][j])表示合并(isim j)段的最大得分，那么转移方程显然为(f[i][j]=max{f[i][k]+f[k][j]}+sum_{k=i}^{j}a[i])，而这个方程的循环顺序显然为从较短长度到较长，而求和我们可以用前缀和处理。

代码

#include <bits/stdc++.h>
using namespace std;

int read()
{
	int res=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
	return res*w;
}

int a[220],sum[440],f1[440][440],f2[440][440];
int main() 
{
	int n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		sum[i]=sum[i-1]+a[i];
	}
	for(int i=1;i<=n;i++)
		sum[i+n]=sum[i+n-1]+a[i];
//	for(int i=1;i<=n*2;i++)
//		printf("%d %d
",i,sum[i]);
	for(int len=2;len<=n;len++)
		for(int l=1;l<=n*2-len+1;l++)
		{
			int r=l+len-1;
			f1[l][r]=0x3f3f3f3f,f2[l][r]=0;
			for(int k=l;k<r;k++)
			{
				f1[l][r]=min(f1[l][r],f1[l][k]+f1[k+1][r]);
				f2[l][r]=max(f2[l][r],f2[l][k]+f2[k+1][r]);
			}
			f1[l][r]+=sum[r]-sum[l-1];
			f2[l][r]+=sum[r]-sum[l-1];
		}
	int ans1=0x3f3f3f3f,ans2=0;
	for(int i=1;i<=n;i++)
	{
		ans1=min(ans1,f1[i][i+n-1]);
		ans2=max(ans2,f2[i][i+n-1]);
	}
	printf("%d
%d",ans1,ans2);
	return 0;
}