给定长度为\(n\)的序列,序列中的每个数有大小\(a_i\),两人轮流可以选择从头或者尾取一个数字,两人取得的总和是\(X\)和\(Y\),两人都希望\(X-Y\)和\(Y-X\)最大,问最终\(X-Y\)是多少
容易想到,每次进行决策我们并不关心之前是怎么取的,只希望现在能够取到最大值
从外向内既然不好考虑,就考虑逆过程。
\(dp[i][j]\)表示从内拓展到\(i-j\)区间的最大差值
为什么是负数呢?因为每次换一个人对他而言就要取个负号
ll dp[3005][3005];
ll a[3005];
int main(){
int n = rd();
for(int i = 1;i <= n;i++)
a[i] = rd();
for(int l = n;l >= 1;l--)
for(int r = l;r <= n;r++)
dp[l][r] = max(a[l] - dp[l + 1][r],a[r] - dp[l][r - 1]);
printf("%lld",dp[1][n]);
}
原文:https://www.cnblogs.com/hznumqf/p/14381100.html