hdu 4579 博弈+区间dp

时间：2022-01-18 05:12:50

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

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxe = ;

const int maxn = ;

const int INF  = 0x3f3f3f;

int dp[maxn][maxn][maxn][maxn];  //dp[l1][r1][l2][r2] 表示先手与后手取得到的最大差值。

bool vis[maxn][maxn][maxn][maxn];

int a[maxn],b[maxn];

int N;

int dfs(int l1,int r1,int l2,int r2){

    if(vis[l1][r1][l2][r2])  return dp[l1][r1][l2][r2];

    vis[l1][r1][l2][r2] = true;

    if(l1>r1 && l2>r2)  return dp[l1][r1][l2][r2] = ;  //这地方必须这样写，不能只写成return 0;

    int ans = -INF;

    if(l1 <= r1){

        ans = max(ans,a[l1] - dfs(l1+,r1,l2,r2));  //dfs(l1+1,r1,l2,r2)表示你先手走了以后，别人作为先手得到的最大差值。所以应该用a[l1]-dfs()表示你作为先手的最大值。

        ans = max(ans,a[r1] - dfs(l1,r1-,l2,r2));

    }

    if(l2 <= r2){

        ans = max(ans,b[l2] - dfs(l1,r1,l2+,r2));

        ans = max(ans,b[r2] - dfs(l1,r1,l2,r2-));

    }

    return dp[l1][r1][l2][r2] = ans;

}

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    while(T--){

        cin>>N;

        memset(dp,-0x3f,sizeof(dp));

        memset(vis,,sizeof(vis));

        int tot = ;

        for(int i=;i<=N;i++)    scanf("%d",&a[i]), tot += a[i];

        for(int i=;i<=N;i++)    scanf("%d",&b[i]), tot += b[i];

        dfs(,N,,N);

        cout<<(dp[][N][][N]+tot)/<<endl;

    }

}

下面是参考别人例外一种好的思路：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxe = ;

const int maxn = ;

const int INF  = 0x3f3f3f;

int dp[maxn][maxn][maxn][maxn];  //dp[l1][r1][l2][r2] 表示先手取得到的最大值。

int a[maxn],b[maxn];

int sum1[maxn],sum2[maxn];

int N;

int dfs(int l1,int r1,int l2,int r2){

    if(dp[l1][r1][l2][r2] != - )     return dp[l1][r1][l2][r2]  ;

    if(l1>r1 && l2>r2)  return ;

    int ans = ;

    int sum = ;

    if(l1 <= r1)  sum += sum1[r1] - sum1[l1-];

    if(l2 <= r2)  sum += sum2[r2] - sum2[l2-];

    if(l1 <= r1){

        ans = max(ans,sum-dfs(l1+,r1,l2,r2));  //避免了直接用dp[l1][r1][l2][r2];

        ans = max(ans,sum-dfs(l1,r1-,l2,r2));

    }

    if(l2 <= r2){

        ans = max(ans,sum-dfs(l1,r1,l2+,r2));

        ans = max(ans,sum-dfs(l1,r1,l2,r2-));

    }

    return dp[l1][r1][l2][r2] = ans;

}

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    while(T--){

        cin>>N;

        memset(dp,-,sizeof(dp));

        sum1[] = ;  sum2[] = ;

        for(int i=;i<=N;i++)    scanf("%d",&a[i]), sum1[i] = sum1[i-] + a[i];

        for(int i=;i<=N;i++)    scanf("%d",&b[i]), sum2[i] = sum2[i-] + b[i];

        cout<<dfs(,N,,N)<<endl;

    }

}

相关文章