比赛 |
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();
}