我们用dfs(state)来表示state状态时,先手-后手的最优值

我们先来看一个简单模型：

假设获得分数后“没有”再来一次的机会,那么A和B肯定是轮流取

则结果就是dp[state]=max(取i的价值-dp[state^(1<<i)]),其中stase&(1<<i)=0

但是,如果获得分数后有奖励,情况就变了

如果在state这个状态取i可以获得分数,就相应获得再来的机会,

那么dp[state^(1<<i)]的价值还是会被在状态state选i的人得到,于是方程变了

dp[state]=max(取i得x分数+dp[state^(1<<i)],取i没得分的情况(就是上面那种情况)),其中state&(1<<i)=0

#include
      
       #include
       
        #include
        
         using namespace std;#define oo (1<<28)struct CNT{    int col[10];};CNT cnt[22];int dp[1<<22];int B,G,S;int dfs(int state,int *b1){    int b2[10];    int ans,res;    int i,j;    if(dp[state]!=-oo)return dp[state];    ans=-oo;    for(i=0;i