NYOJ737——石子合并(1) -电脑资料

石子合并（一）

描述 有N堆石子排成一排，每堆石子有一定的数量，

NYOJ737——石子合并(1)

。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。

输入有多组测试数据，输入到文件结束。

    每组测试数据第一行有一个整数n，表示有n堆石子。

    接下来的一行有n（0< n<200）个数，分别表示这n堆石子的数目，用空格隔开输出输出总代价的最小值，占单独的一行样例输入

31 2 3713 7 8 16 21 4 18

样例输出

9239

来源

    经典问题

    区间dp，设dp[i][j]表示合并第i堆石子导第j堆石子所花的最小代价，那么dp[i][j] = min(dp[i][k] + dp[k + 1][j] + sum[i][j])

   

#include<map>#include<set>#include<li>#include<stack>#include<queue>#include<vector>#include<cmath>#include<cstdio>#include<cstring>#include<iostream>#include     using namespace std;const int N = 220;const int inf = 0x3f3f3f3f; int w[N];int dp[N][N];int sum[N];int main(){	int n;	while (~scanf("%d", &n))	{		sum[0] = 0;		for (int i = 1; i<= n; i++)		{			scanf("%d", &w[i]);			sum[i] = sum[i - 1] + w[i];		}		memset (dp, 0, sizeof(dp));		for (int i = n; i >= 1; i--)		{			for (int j = i + 1; j<= n; j++)			{				int tmp = inf;				for (int k = i; k< j; k++)				{					tmp = min(tmp, dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);				}				dp[i][j] = tmp;			}		}		printf("%d\n", dp[1][n]);	}	return 0;}