本题考虑记忆化搜索
表示当前玩家从堆的,堆的能获得的最大价值
转移方程为:
int maxa = 0, maxb = 0;
if (x <= y)
maxa = mx(a[x] + dfs(x + 1, y, i, j), a[y] + dfs(x, y - 1, i, j));
if (i <= j)
maxb = mx(b[i] + dfs(x, y, i + 1, j), b[j] + dfs(x, y, i, j - 1));
dp[x][y][i][j] = suma[y] - suma[x - 1] + sumb[j] - sumb[i - 1] - mx(maxa, maxb);
//区间和减去对手所取的剩下的就为当前玩家的