题目链接 题意：一排硬币有不同的价值，只能从左到右拿，下一个人最多可以拿上一个人拿的硬币数量的两倍，A先拿，且第一次最多只能拿两枚硬币，问A拿的硬币的价值和最大为多少。
这道题和A Game类似，我们用dp[i][j]表示当剩下i枚硬币且上一次拿硬币的人取走了j枚硬币时可以取得的最大价值,（下列说明默认不超出范围）dp[i][j]状态下,可以取(k=n-i+1)k,k+1,k+2…k+2j-1,dp[i][j-1]状态下,可以取k,k+1,k+2…k+2j-3,两者之间差了k+2j-2,k+2j-1,所以dp[i][j]从dp[i][j-1]转移至dp[i][j]的方程为dp[i][j]=dp[i][j-1];dp[i][j]=max(dp[i][j],sum[i]-dp[i-2*j][2*j],sum[i]-dp[i-2*j-1][2*j-1]),sum[i]-dp[i-2*j][2*j]是指如果这步取了2j个硬币，那么后继状态即为dp[i-2j][2j],而该状态是另一个人拿的，所以剩下的价值是哪2j个硬币可以取得的价值，而每一个dp[i][j]都是在保证上一状态最大的情况下转移过来的，也符合双方都尽可能使自己拿到的硬币的价值和最大的特点。
AC代码
#include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N = 2020; int arr[N], dp[N][N],sum[N];//不需要开long long,我脑抽没看范围开了long long然后MLE了 int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; } for (int i = n; i >= 1; i--) { sum[n - i +1] = sum[n - i] + arr[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (i >= 2 * j ) dp[i][j] = max(dp[i][j], sum[i] - dp[i - 2 * j ][2 * j]); if (i >= 2 * j - 1 ) dp[i][j] = max(dp[i][j], sum[i] - dp[i - 2 * j + 1][2 * j - 1]); } } cout << dp[n][1] << endl; }