HDU 4597（记忆化搜索 dfs 参考）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4597

2 
 
1 
23 
53 
 
3 
10 100 20 
2 4 3 

53 
105 

PS:

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 32;
int a[maxn], b[maxn], suma[maxn], sumb[maxn];
int dp[maxn][maxn][maxn][maxn];
//dp[x][y][i][j]表示当前玩家从a堆的x~y,b堆的i~j能获得的最大价值 
int dfs(int x, int y, int i, int j)
{
    if(dp[x][y][i][j])
    {
        return dp[x][y][i][j];
    }
    if(x > y && i > j)
    {
        return 0;
    }
    int maxa = 0, maxb = 0;
    if(x <= y)
    {
        maxa = max(a[x]+dfs(x+1,y,i,j),a[y]+dfs(x,y-1,i,j));
    }
    if(i <= j)
    {
        maxb = max(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]-max(maxa,maxb);
    
    //区间和减去对手所取的剩下的就为当前玩家的
    return dp[x][y][i][j];
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        memset(suma, 0,sizeof(suma));
        memset(sumb, 0,sizeof(sumb));
        int n;
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            suma[i] = suma[i-1]+a[i];
        }
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&b[i]);
            sumb[i] = sumb[i-1]+b[i];
        }
        int ans = suma[n]+sumb[n]-dfs(1,n,1,n);
        printf("%d\n",ans);
    }
    return 0;
}

HDU 4597（记忆化搜索 dfs 参考）

原文：http://blog.csdn.net/u012860063/article/details/45604309