记录编号 |
20396 |
评测结果 |
AAAAAAAAAA |
题目名称 |
整理书本 |
最终得分 |
100 |
用户昵称 |
郭乾乐 |
是否通过 |
通过 |
代码语言 |
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;
}