发布于2018年8月12日 由itewqq[搜索][博弈][模板] HDU 4597 Play Game https://cn.vjudge.net/problem/HDU-4597 对抗搜索模板题。裸的minimax算法，搜索的时候注意max层要加上点的值，还没有仔细学α-β剪枝所以没用。。。 只用了记忆化（似乎也没什么卵用啊） 不过这个数据量，基础算法足够了。 #include #include #include #include #include #include #include #include #include #include #include #include #include //#include using namespace std; typedef long long LL; const int maxn=10000+5; const int MOD=1e9+7; const int INF=0x3f3f3f3f; int card[2][maxn]; int vis[22][22][22][22][2]; int dfs(int ha,int ta,int hb,int tb,int m)//m==1 max , m==0 min { if(vis[ha][ta][hb][tb][m]!=-1) return vis[ha][ta][hb][tb][m]; if(ha>ta&&hb>tb) return vis[ha][ta][hb][tb][m]=0; int best; if(m) { best=-INF; if(ha<=ta) { best=max(best,card[0][ha]+dfs(ha+1,ta,hb,tb,0)); best=max(best,card[0][ta]+dfs(ha,ta-1,hb,tb,0)); } if(hb<=tb) { best=max(best,card[1][hb]+dfs(ha,ta,hb+1,tb,0)); best=max(best,card[1][tb]+dfs(ha,ta,hb,tb-1,0)); } } else { best=INF; if(ha<=ta) { best=min(best,dfs(ha+1,ta,hb,tb,1)); best=min(best,dfs(ha,ta-1,hb,tb,1)); } if(hb<=tb) { best=min(best,dfs(ha,ta,hb+1,tb,1)); best=min(best,dfs(ha,ta,hb,tb-1,1)); } } return vis[ha][ta][hb][tb][m]=best; } int main() { int T,n; scanf("%d",&T); while(T--) { memset(vis,-1,sizeof(vis)); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&card[0][i]); for (int i=1;i<=n;i++) scanf("%d",&card[1][i]); int ans=dfs(1,n,1,n,1); printf("%d\n",ans); } return 0; }
