博弈论（2）DP/记忆化搜索
博弈问题的话，假设两个人都极度聪明，都会采取最优策略，那么就是也知道了对方也和自己一样聪明，我采取最优策略后，对方也会根据当前状态做出最优策略，简而言之，就是每个玩家都从第一步棋看到了最后一步棋。
先手控局，棋还没下，就已经知道走哪一步会获得什么样的结果。
那么，现代化的我们就可以用计算机根据每个状态下必取最优策略的原则，提前搜索出所有情况。
再次强调，最优是针对的状态，上文已经说过两人都是满智力奇才，面临什么样的状态就代表面临着什么样的结局。
常用算法：记忆化搜索，状压DP。
根据我的经验，博弈都是逆推，这也和上面提到的博弈的性质有关，对当前状态进行决策时，必然要先知道所有后续状态的最优嘛。
例题：
http://poj.org/problem?id=1678
题意：有N个数，有一个区间[A,B]，先手先取一个数x（必须A<=x<=B），后手取一个数y（必须A+x<=y<=B+x），再先手取一个数z（必须A+y<=z<=B+y），，直到不能取，求先手所取数之和-后手所取数之和
把先手当做收益，后手当做损失，那么这题就好比求先手所面临状态的最大收益
发现这个题后面的状态不能影响前面的状态，那么便可以记忆化搜索，时间复杂度不高。
这里的状态就是区间，决策就是取一个在这个区间里的数。
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int inf=1000000000; 6 int used[30005],dp[30005],a0,b0; 7 int dfs(int a,int b,int x)//已选择x， 【a，b】为对方面临的状态 8 { if(dp[x]!=-inf) return dp[x]; 9 int num=0,res=-inf; 10 for(int i=a;i<=b;i++)//对方在【a，b】所能达到的最大收益 11 { if(!used[i]) continue; 12 used[i]--; 13 res=max(res,dfs(a0+i,b0+i,i)); 14 15 used[i]++; 16 num++; 17 } 18 if(num==0) return dp[x]=x; 19 else return dp[x]=x-res; 20 } 21 int main() 22 { int T; 23 scanf("%d",&T); 24 while(T--) 25 { int n; 26 memset(used,0,sizeof(used)); 27 for(int i=1;i<=10000;i++) 28 dp[i]=-inf; 29 30 scanf("%d%d%d",&n,&a0,&b0); 31 for(int i=0;i<n;i++) 32 { 33 int x; 34 scanf("%d",&x); 35 if(x>0) used[x]++; 36 } 37 int res=-inf,num=0; 38 for(int i=a0;i<=b0;i++) 39 { if(!used[i]) continue; 40 used[i]--; 41 res=max(res,dfs(a0+i,b0+i,i)); 42 43 used[i]++; 44 num++; 45 } 46 if(num==0) res=0; 47 printf("%d ",res); 48 49 50 51 } 52 53 54 55 56 return 0; 57 }