题意:有n颗石子 两个人轮流拿 如果上一个人拿了x颗 这个人就可以拿x或x+1颗
问先手能获得与后手的价值差最大是多少
题解:看起来是博弈 其实是DP
dp[i][j][0/1]表示当前该0/1拿 拿到第i颗上一个人拿了j个 转移就很裸了
因为当前有两种操作拿x个和拿x+1个 要知道哪一个操作更好 需要知道后面的状态 所以就倒着DP
因为爆内存就滚动了 对2^k取% = & 2^k - 1 感觉这样滚动会少个常数
#include <bits/stdc++.h> using namespace std; int q[20005]; int sum[20005]; int dp[265][205][2]; int main() { int T; scanf("%d", &T); while(T--) { sum[0] = 0; int n; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &q[i]), sum[i] = sum[i - 1] + q[i]; memset(dp, 0, sizeof(dp)); for(int i = n; i >= 1; i--) { for(int j = 1; j <= 200; j++) { if(i + j == n + 1) { dp[i & 255][j][1] = sum[n] - sum[i - 1]; dp[i & 255][j][0] = sum[i - 1] - sum[n]; break; } dp[i & 255][j][1] = max(dp[(i + j) & 255][j][0], dp[(i + j + 1) & 255][j + 1][0] + q[i + j]) + sum[i + j - 1] - sum[i - 1]; dp[i & 255][j][0] = min(dp[(i + j) & 255][j][1], dp[(i + j + 1) & 255][j + 1][1] - q[i + j]) - sum[i + j - 1] + sum[i - 1]; } } printf("%d ", dp[1][1][1]); } return 0; }