有两个双端队列每次每人可以从任意一堆的头或尾取值,两人均采取最优策略,问先手的最后得分
很简单的博弈
#include#include #include using namespace std;const int inf = 1000000000;int T, N, A[25], B[25], f[25][25][25][25];int DP(int a, int b, int c, int d) { int turn = N - (b - a + 1) + N - (d - c + 1); if(turn == (N << 1)) return 0; int & res = f[a][b][c][d]; if(res != -1) return res; if(turn & 1) { res = inf; if(a <= b) res = min(res, DP(a + 1, b, c, d)); if(a <= b) res = min(res, DP(a, b - 1, c, d)); if(c <= d) res = min(res, DP(a, b, c + 1, d)); if(c <= d) res = min(res, DP(a, b, c, d - 1)); } else { res = 0; if(a <= b) res = max(res, DP(a + 1, b, c, d) + A[a]); if(a <= b) res = max(res, DP(a, b - 1, c, d) + A[b]); if(c <= d) res = max(res, DP(a, b, c + 1, d) + B[c]); if(c <= d) res = max(res, DP(a, b, c, d - 1) + B[d]); } return res;}int main() { scanf("%d", &T); for(int kase = 1; kase <= T; kase++) { scanf("%d", &N); for(int i = 1; i <= N; i++) { scanf("%d", &A[i]); } for(int i = 1; i <= N; i++) { scanf("%d", &B[i]); } memset(f, -1, sizeof(f)); printf("%d\n", DP(1, N, 1, N)); } return 0;}