石子合并

题目链接：http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=737

想了很久，PPT上是这样写的- -然后我就按照PPT上说的写下状态转移方程，在1 2 3这个样例中一直都是6  囧rz。

终于抛开了PPT的状态转移方程，去想区间DP的思路。想到了dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+t[i,j])。

附上代码：

<span style="font-size:12px;">#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 0x7fffffff
int dp[205][205],sum[205];
int a[205];
int min(int x,int y)
{
	if(x<y)
		return x;
	return y;
}
int main()
{
	int i,j,n;
	while(scanf("%d",&n)!=EOF)
	{
		memset(sum,0,sizeof(sum));
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i]=sum[i-1]+a[i];
		}
		for(int v=1;v<=n;v++)  
		{  
			for(int i=1;i<=n-v;i++)  
			{  
				int j = i + v;  
				dp[i][j] = INF;  
				int tmp = sum[j] - sum[i-1];
				for(int k=i;k<j;k++)  
					dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j] + tmp);  
			}  
		}
		printf("%dn",dp[1][n]);
	}
	return 0;
}
</span>

最后

以上就是欢喜雪糕为你收集整理的石子合并的全部内容，希望文章能够帮你解决石子合并所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。