DTGAME - Tiền bạc luôn là thứ quý giá
Tác giả: ll931110
Ngôn ngữ: C++
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
int f[2020][2020],pos[2020][2020];
int a[2020];
int n;
int main()
{
// freopen("game.in","r",stdin);
// freopen("game.ou","w",stdout);
scanf("%d", &n);
a[0] = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 2; i <= n; i++) a[i] += a[i - 1];
memset(f,0,sizeof(f));
for (int i = 1; i <= n; i++) pos[i][i] = i;
for (int len = 2; len <= n; len++)
for (int i = 1; i <= n - len + 1; i++)
{
int j = i + len - 1;
for (int t = pos[i][j - 1]; t <= pos[i + 1][j]; t++) if (t > 1)
{
int tmp = min(a[t - 1] - a[i - 1] + f[i][t - 1],a[j] - a[t - 1] + f[t][j]);
if (f[i][j] < tmp)
{
f[i][j] = tmp; pos[i][j] = t;
}
}
}
printf("%d\n", f[1][n]);
}