HDU4597(博弈dp)

题意：爱丽丝和鲍勃正在玩游戏。有两个成堆的卡片。每一堆有N个卡片,每张卡片有一个分数。他们轮流接顶部或底部拿卡片,卡的分数将被添加到他的总分。爱丽丝和鲍勃都足够聪明,拿起牌来获得尽可能多的分数。爱丽丝先手最多能拿多少分?

题解：经典博弈dp
设置状态dp[l1][r1][l2][r2]：
l1-r1：指第一堆余下的为从下面 l1 位置开始到 r1 位置
l2-r2: 同理
dp[l1][r1][l2][r2]即为在这种状态下Alice的最多得分
总共可以从四个状态转移过来，第一堆取最后一个/最顶上一个，第二堆取最后一个/最顶上一个。以取第一堆最后一个为例，该值=a[l1]+余下所有石子的分值-Bob的最优取法，其余三种同理。
附代码：`

#include <bits/stdc++.h>
#define inf 2333333333333333
#define N 1000010
#define p(a) putchar(a)
#define For(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
void in(int &x){
    int y=1;char c=getchar();x=0;
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    x*=y;
}
void o(int x){
    if(x<0){p('-');x=-x;}
    if(x>9)o(x/10);
    p(x%10+'0');
}
int a[50],b[50];
int d[50][50][50][50];
int sum1[50];
int sum2[50];
int dfs(int l1,int r1,int l2,int r2){
	if(d[l1][r1][l2][r2]!=-1) return d[l1][r1][l2][r2];
	d[l1][r1][l2][r2]=0;
	if(l1<=r1) d[l1][r1][l2][r2]=max(d[l1][r1][l2][r2],a[l1]+sum1[r1]-sum1[l1]+sum2[r2]-sum2[l2-1]-dfs(l1+1,r1,l2,r2));
	
	if(l1<=r1) d[l1][r1][l2][r2]=max(d[l1][r1][l2][r2],a[r1]+sum1[r1-1]-sum1[l1-1]+sum2[r2]-sum2[l2-1]-dfs(l1,r1-1,l2,r2));
	
	if(l2<=r2) d[l1][r1][l2][r2]=max(d[l1][r1][l2][r2],b[l2]+sum1[r1]-sum1[l1-1]+sum2[r2]-sum2[l2]-dfs(l1,r1,l2+1,r2));
	
	if(l2<=r2) d[l1][r1][l2][r2]=max(d[l1][r1][l2][r2],b[r2]+sum1[r1]-sum1[l1-1]+sum2[r2-1]-sum2[l2-1]-dfs(l1,r1,l2,r2-1));
	
	return d[l1][r1][l2][r2];
}
signed main()
{
	int t;
	in(t);
	while(t--){
		int n;
		in(n);
		memset(d,-1,sizeof(d));
		sum1[0]=sum2[0]=0;
		for(int i=1;i<=n;i++){
			in(a[i]);
			sum1[i]=sum1[i-1]+a[i];
			
		}
		for(int i=1;i<=n;i++){
			in(b[i]);
			sum2[i]=sum2[i-1]+b[i];
			
		}
		o(dfs(1,n,1,n));
		p('\n');
	}
} 

因为最近在刷博弈论的题，所以写博客记录一下
第一次写博客，如有不好请指教qwq

本文地址：https://blog.csdn.net/qikik/article/details/107899771