记录编号 20396 评测结果 AAAAAAAAAA
题目名称 整理书本 最终得分 100
用户昵称 Gravatar郭乾乐 是否通过 通过
代码语言 C++ 运行时间 0.442 s
提交时间 2010-10-25 22:20:54 内存使用 1.41 MiB
显示代码纯文本
#include<iostream>
#include<fstream>
using namespace std;

int main()
{
	ifstream fin("book.in");
	ofstream fout("book.out");
	int n,a[401],x,y,f[401][401],v[401][401],i,j,k,r;
	fin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			f[i][j]=0;
		fin>>x>>y;
		a[i]=x-y;
	}
	for(i=1;i<=n;i++) 
	{
		v[i][i]=a[i];
		for(j=i+1;j<=n;j++)
			v[i][j]=v[i][j-1]+a[j];
	}
	for(i=1;i<n;i++)
		for(j=1;j<=n-i;j++)
		{
			k=j+i;
			f[j][k]=99999999;
			for(r=j;r<k;r++)
				if((f[j][r]+f[r+1][k]+v[j][k])<f[j][k]) f[j][k]=f[j][r]+f[r+1][k]+v[j][k];
		}
	fout<<f[1][n]<<endl;
	return 0;
}