hdu 4579 博弈+区间dp

题目链接：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 = 50000;
const int maxn = 26;
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] = 0;  //这地方必须这样写，不能只写成return 0;
    int ans = -INF;

    if(l1 <= r1){
        ans = max(ans,a[l1] - dfs(l1+1,r1,l2,r2));  //dfs(l1+1,r1,l2,r2)表示你先手走了以后，别人作为先手得到的最大差值。所以应该用a[l1]-dfs()表示你作为先手的最大值。
        ans = max(ans,a[r1] - dfs(l1,r1-1,l2,r2));
    }
    if(l2 <= r2){  
        ans = max(ans,b[l2] - dfs(l1,r1,l2+1,r2));
        ans = max(ans,b[r2] - dfs(l1,r1,l2,r2-1));
    }
    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,0,sizeof(vis));
        int tot = 0;
        for(int i=1;i<=N;i++)    scanf("%d",&a[i]), tot += a[i];
        for(int i=1;i<=N;i++)    scanf("%d",&b[i]), tot += b[i];

        dfs(1,N,1,N);
        cout<<(dp[1][N][1][N]+tot)/2<<endl;
    }
}

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int maxe = 50000;
const int maxn = 26;
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] != -1 )     return dp[l1][r1][l2][r2]  ;
    if(l1>r1 && l2>r2)  return 0;
    int ans = 0;
    int sum = 0;
    if(l1 <= r1)  sum += sum1[r1] - sum1[l1-1];
    if(l2 <= r2)  sum += sum2[r2] - sum2[l2-1];

    if(l1 <= r1){
        ans = max(ans,sum-dfs(l1+1,r1,l2,r2));  //避免了直接用dp[l1][r1][l2][r2];
        ans = max(ans,sum-dfs(l1,r1-1,l2,r2));
    }
    if(l2 <= r2){
        ans = max(ans,sum-dfs(l1,r1,l2+1,r2));
        ans = max(ans,sum-dfs(l1,r1,l2,r2-1));
    }
    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,-1,sizeof(dp));
        sum1[0] = 0;  sum2[0] = 0;
        for(int i=1;i<=N;i++)    scanf("%d",&a[i]), sum1[i] = sum1[i-1] + a[i];
        for(int i=1;i<=N;i++)    scanf("%d",&b[i]), sum2[i] = sum2[i-1] + b[i];

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