本文共 2396 字，大约阅读时间需要 7 分钟。
本文出自
sum(i, j, k, l) - 上一次Bob拿的值就等于Alice能拿到的值
f(i, j, k, l) = sum(i, j, k, l) - min{ f(i+1, j, k, l) f(i, j-1, k, l) f(i, j, k+1, l) f(i, j, k, l-1) }
/**===================================================== * This is a solution for ACM/ICPC problem * * @source : hdu-4597 Play Game * @description : 区间dp * @author : shuangde * @blog : blog.csdn.net/shuangde800 * @email : zengshuangde@gmail.com * Copyright (C) 2013/08/24 15:12 All rights reserved. *======================================================*/#include #include #include using namespace std;int n;int a[22], b[22];int f[22][22][22][22];int sum1[22], sum2[22];int dfs(int a1, int a2, int b1, int b2) { int& ans = f[a1][a2][b1][b2]; int now; if (a1 > a2){ now = sum2[b2] - sum2[b1-1]; if (b1==b2) ans = now; } else if( b1 > b2) { now = sum1[a2] - sum1[a1-1]; if (a1==a2) ans = now; } else { now = sum1[a2] - sum1[a1-1] + sum2[b2] - sum2[b1-1]; } if (ans != -1) return ans; ans = 0; if (a1 <= a2) { ans = max(ans, now - min(dfs(a1+1, a2, b1, b2), dfs(a1, a2-1, b1, b2))); } if (b1 <= b2) { ans = max(ans, now - min(dfs(a1, a2, b1+1, b2), dfs(a1, a2, b1, b2-1))); } return ans;}int main() { int nCase; scanf("%d", &nCase); while (nCase--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sum1[i] = sum1[i-1] + a[i]; } for (int i = 1; i <= n; ++i) { scanf("%d", &b[i]); sum2[i] = sum2[i-1] + b[i]; } memset(f, -1, sizeof(f)); cout << dfs(1, n, 1, n) << endl; } return 0;}