比赛 20101025 评测结果 AWWWWWWWWW
题目名称 整理书本 最终得分 10
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-10-25 20:58:42
显示代码纯文本
#include <fstream>

#define I_F "book.in"
#define O_F "book.out"
#define MAX 400

using namespace std;

short n;
short s[MAX];
int ans;

void Input();
void Dyna();
void Output();

int main()
{
	Input();
	Dyna();
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n;
	short w,v;
	for (short i=0; i<n; i++)
	{
		fin>>w>>v;
		s[i]=w-v;
	}
	fin.close();
}

void Dyna()
{
	int sum[MAX][MAX]={{s[0]}};
	short i,j,k;
	int t;
	
	for (i=1; i<n; i++)
		sum[0][i]=s[i]+sum[0][i-1];
	for (i=1; i<n; i++)
		for (j=i; j<n; j++)
			sum[i][j]=sum[0][j]-sum[0][i-1];
		
	int f[MAX][MAX]={{0}};
	for (i=0; i<n; i++)
		f[i][i]=s[i];
	for (i=1; i<n; i++)
		for (j=0; j<n-i; j++)
		{
			t=2000000000;
			for (k=j; k<j+i; k++)
				if (f[j][k]+f[k+1][i+j]<t)
					t=f[j][k]+f[k+1][i+j];
			f[j][i+j]=t+sum[j][i+j];
		}
	ans=sum[0][n-1];
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}