记录编号	32652	评测结果	AAAAAAAAAA
题目名称	整理书本	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.247 s
提交时间	2011-11-07 16:06:00	内存使用	0.87 MiB

#include <cstdio>
using namespace std;

int f[401][401]={{0}};

int main(void)
{
	freopen("book.in","r",stdin);
	freopen("book.out","w",stdout);
	int i,j,k,n,temp,wei[401]={0},val[401]={0},cal[401]={0};
	scanf("%d\n",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d %d\n",&wei[i],&val[i]);
		cal[i]=cal[i-1]+wei[i]-val[i];
	}
	for (j=2;j<=n;j++)
	{
		for (i=1;i<=n-j+1;i++)
		{
			f[i][j]=2000000000;
			for (k=1;k<=j-1;k++)
			{
				temp=f[i][k]+f[i+k][j-k]+cal[i+j-1]-cal[i-1];
				if (temp<f[i][j])
					f[i][j]=temp;
			}
		}
	}
	printf("%d\n",f[1][n]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}