DTGAME - Tiền bạc luôn là thứ quý giá
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
long min(long x,long y)
{
if(x<y) return x;
else return y;
}
main()
{
long n,a[2001],cat[2001][2001],f[2001][2001],tong[2001][2001],max;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
scanf("%ld",&a[i]);
for(long i=1;i<=n;i++)
for(long j=i;j<=n;j++)
{
if(i==j)
tong[i][j]=a[i];
else tong[i][j]=tong[i][j-1]+a[j];
//printf("%ld\n",tong[i][j]);
}
for(long i=1;i<=n;i++)
f[i][i]=0;
for(long i=1;i<=n-1;i++)
{
f[i][i+1]=min(a[i],a[i+1]);
cat[i][i+1]=i;
//printf("%ld\n",f[i][i+1]);
}
for(long i=3;i<=n;i++)
for(long j=1;j<=n-i+1;j++)
{
max=0;
//if(j==1&&i==3)
//printf("%ld %ld %ld %ld %ld %ld\n",cat[1][2],cat[2][3],f[1][2],f[2][3],tong[1][2],tong[2][3]);
for(long k=cat[j][j+i-2];k<=cat[j+1][j+i-1];k++)
{
if(min(f[j][k]+tong[j][k],f[k+1][j+i-1]+tong[k+1][j+i-1])>max)
{
max=min(f[j][k]+tong[j][k],f[k+1][j+i-1]+tong[k+1][j+i-1]);
cat[j][j+i-1]=k;
}
}
f[j][j+i-1]=max;
//printf("%ld %ld %ld %ld\n",j,j+i-1,cat[j][j+i-1],f[j][j+i-1]);
}
printf("%ld",f[1][n]);
//getch();
}