本文主要是介绍hdu 4597 Play Game （记忆化搜索,区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
有两个人玩取数的游戏，每次只能从两堆数列的两头取一个数，问先取的那个人最大能够获得的数是多少。
解题思路：
有题解说是记忆化搜索，很显然，我用了4维dp保存结果。dp[i][j][k][t] 表示 第一行为第i个数字到第j个数字，第二行为第k个数字到第t个数字的时候，我能够取得的最大值。
这边有个小问题，就是在状态转移的时候，我们要取几种可能状态下的最小值，虽然dp整个表示的是最大值。
试想：我要使自己获得的数字总和最大，那么相当于使对方获得的数字总和最小，所以在取数字的时候，尽可能地把使对方获得的数字最小的状态留给对手。
所以，对于dp[i][j][k][t] 我是取i的位置呢还是取j的位置呢还是取k或者t的位置，要根据留给对方的数字总和最小这一原则去取。如果留给对手的可能性一样，那么取加上该位置后使自己最大的数。
另外，在状态转移的时候，其实是从上上的状态转移到当前状态。因为，我在取的时候，对方也有一个取过了。然后，一样的，转移过来的时候，应该取一个较小的，因为对手只会给自己留下最小总和的状态。
最终的答案是dp[1][n][1][n]。这个记忆化搜索，跟一般的记忆化搜索还是有点不一样的。
具体看代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
int vis[25][25][25][25];
//dp[i][j][k][t] 表示 第一行为第i个数字到第j个数字，第二行为第k个数字到第t个数字的时候，我能够取得的最大值
//dp保存的是最大能取得的数，但是在状态转移的时候，应该转移多种状态下的最小值
int dp[25][25][25][25];
int a[25];
int b[25];
int minl(int x1,int x2,int x3,int x4)
{int x = x1;if(x>x2)x=x2;if(x>x3)x=x3;if(x>x4)x=x4;return x;
}
int DP(int i,int j,int k,int t)
{if(vis[i][j][k][t]==1)return dp[i][j][k][t];vis[i][j][k][t]=1;//不满足要求的情况下，赋值为最大//这种情况在本身传递过来的时候就已经不满足要求if(i>j+1||k>t+1)return dp[i][j][k][t]=100000000;//当两边的下标都超出范围的时候，赋值为0//不同于上一条，因为恰好超出范围的时候，是有可能从满足要求的那边传递过来的if(i>j&&k>t)return dp[i][j][k][t]=0;//只有一个元素的时候if(i>j&&k==t)return dp[i][j][k][t]=b[k];else if(i==j&&k>t)return dp[i][j][k][t]=a[i];else{//我要最大，那么就是要让对手最小int t1 = minl(DP(i+1,j,k,t),DP(i,j-1,k,t),DP(i,j,k+1,t),DP(i,j,k,t-1));//这边我一开始写的是max错了很多次，我认为是要选择在对手最小的情况下选择最大的，结果一直不对//改成minl的时候，就对了。理由很简单，在我给对手最小的情况的时候，对手肯定也会给我留最小的。所以我的状态应该是从最小的那边传过来的//然后，我应该在所有的可能的情况下选择一个最优的方案。if(t1==dp[i][j][k+1][t])dp[i][j][k][t]=max(dp[i][j][k][t],b[k]+minl(DP(i,j,k+2,t),DP(i,j,k+1,t-1),DP(i+1,j,k+1,t),DP(i,j-1,k+1,t)));if(t1==dp[i][j][k][t-1])dp[i][j][k][t]=max(dp[i][j][k][t],b[t]+minl(DP(i,j,k,t-2),DP(i,j,k+1,t-1),DP(i+1,j,k,t-1),DP(i,j-1,k,t-1)));if(t1==dp[i+1][j][k][t])dp[i][j][k][t]=max(dp[i][j][k][t],a[i]+minl(DP(i+2,j,k,t),DP(i+1,j-1,k,t),DP(i+1,j,k+1,t),DP(i+1,j,k,t-1)));if(t1==dp[i][j-1][k][t])dp[i][j][k][t]=max(dp[i][j][k][t],a[j]+minl(DP(i,j-2,k,t),DP(i+1,j-1,k,t),DP(i,j-1,k+1,t),DP(i,j-1,k,t-1)));return dp[i][j][k][t];}
}
int main()
{int T,n,m,i,j,k,t;while(scanf("%d",&T)==1){while(T--){scanf("%d",&n);for(i=1; i<=n; i++){scanf("%d",&a[i]);}for(i=1; i<=n; i++){scanf("%d",&b[i]);}memset(vis,0,sizeof(vis));memset(dp,0,sizeof(dp));printf("%d\n",DP(1,n,1,n));}}return 0;
}
这篇关于hdu 4597 Play Game （记忆化搜索,区间dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
