这道题还是去长春之前看的，当时以为是博弈什么的。后来学长说是记忆化搜索，当时连简单的DP都不会，只好先扔到一边了。
dp[s1][e1][s2][e2] 表示第一排剩[s1,e1] ,第二排剩 [s2,e2] 时的最优决策。
dp[s1][e1][s2][ e2 ] = sum - min(dfs(s1,e1,s2+1,e2),dfs(s1,e1,s2,e2-1),dfs(s1+1,e1,s2,e2),dfs(s1,e1-1,s2,e2))。注意边界。
sum表示当前状态下两排数的总和。
A取时，要保证B在下一回合的最优决策最小。既保证自己在这一回合的决策最优。
#include#include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-6) #define LL long long #define ULL unsigned long long int #define _LL __int64 #define _INF 0x3f3f3f3f #define Mod 1000000007 using namespace std; int dp[22][22][22][22]; int num[3][21]; int ans[3][21]; int dfs(int s1,int e1,int s2,int e2) { if(s1 > e1 && s2 > e2) { return 0; } if(dp[s1][e1][s2][e2] != -1) return dp[s1][e1][s2][e2]; if(s1 > e1) { dp[s1][e1][s2][e2] = ans[2][e2] - ans[2][s2-1] - min(dfs(s1,e1,s2+1,e2),dfs(s1,e1,s2,e2-1)); } else if(s2 > e2) { dp[s1][e1][s2][e2] = ans[1][e1] - ans[1][s1-1] - min(dfs(s1+1,e1,s2,e2),dfs(s1,e1-1,s2,e2)); } else { int t1 = ans[2][e2] - ans[2][s2-1] + ans[1][e1] - ans[1][s1-1] - min(dfs(s1,e1,s2+1,e2),dfs(s1,e1,s2,e2-1)); int t2 = ans[2][e2] - ans[2][s2-1] + ans[1][e1] - ans[1][s1-1] - min(dfs(s1+1,e1,s2,e2),dfs(s1,e1-1,s2,e2)); dp[s1][e1][s2][e2] = max(t1,t2); } return dp[s1][e1][s2][e2]; } int main() { int T,n,i; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i = 1;i <= n; ++i) { scanf("%d",&num[1][i]); } for(i = 1;i <= n; ++i) { scanf("%d",&num[2][i]); } ans[1][0] = 0; ans[2][0] = 0; for(i = 1;i <= n; ++i) { ans[1][i] = ans[1][i-1] + num[1][i]; ans[2][i] = ans[2][i-1] + num[2][i]; } memset(dp,-1,sizeof(dp)); dfs(1,n,1,n); printf("%d\n",dp[1][n][1][n]); } return 0; }