DTGAME - Tiền bạc luôn là thứ quý giá
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <cstdio>
using namespace std;
int n, a[2020], s[2020], F[2020][2020], T[2020][2020];
int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) scanf("%d", a+i);
for(int i=1;i<=n;++i) s[i] = a[i-1] + s[i-1];
for(int i=n-1;i>=0;--i) {
T[i][i] = i;
for(int j=i+1;j<n;++j) {
for(int t=T[i][j-1];t<=T[i+1][j];++t) if(i<t) {
int v = (F[i][t-1] + s[t]-s[i]) <? (F[t][j] + s[j+1] - s[t]);
if(F[i][j] < v) {
F[i][j] = v;
T[i][j] = t;
}
}
}
}
printf("%d\n", F[0][n-1]);
return 0;
}