HDU 4597 Play Game 記憶化搜索

這道題還是去長春之前看的，當時以為是博弈什麼的。後來學長說是記憶化搜索，當時連簡單的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;
}