题目链接

当时现场A了这道题，成功以非正式的身份吓到了正式选手。后来听讲解发现好像和我的思路不太一样，所以发一下我的做法

思考方向

考试的时候我就想，这可能是个博弈论，也可能是个DP

博弈论的话由于不是标准的求先手必胜还是必败，所以应该不是了。

那么就是DP了。而且是10*10的，应该是个状压DP。所以先确定了总体思路：状压DP

关于A和B的处理

居然一个格子有两个参数，这样一下就复杂了，要是能变成一个就好了。

所以我试了各种方法（太过复杂不予描述），成功找到了正解：

ans最开始不设为0，设为所有B的和的相反数，然后把格子里A和B加起来就可以正常玩了。

Player1和Player2轮流落子，P1想让结果尽量大，P2落子不计算得分，想让结果尽量小。

如何状压

题目明显是在和我们说每一行棋子一定是左边的一串，并且这一串长度不会超过上面一串。10的二进制位为1010，4位。那么10个10放在一起就是40位，没有超过long long，状压成功。

二进制1010 1001 1000 0111 0110 0101 0100 0011 0010 0001的意思就是第一行10子，二行9子，3行8子，4行7子……10行1子

DP状态的设定

我们肯定不能开1 << 40这么大的DP数组，所以需要离散化。那就DFS一遍枚举所有状态并且用map水一下就好了，反正开O2

我们知道如果一个状态确定了，那轮到谁就也确定了。所以dp[i]就索性设定为状态i下按最优策略博弈还能拿到的分数好了。

但是我比较懒，即使想到了也不想这么写，还不如干脆dp[i][1]为“下一步轮到第1个人走，那么最优策略下还能得到的分数是多少”，dp[i][0]为“下一步轮到第2个人走，那么最优策略下还能得到的分数是多少”

DP的转移方程

dp[now][0] = min(dp[下一个状态][1]);

dp[now][1] = max(dp[下一个状态][0] + 到达状态能得到的分数);

OK，那到达状态能得到的分数怎么办？

到达状态能得到的分数

肯定就是现在的比后来的多出来的那一格的得分了，这个大家看我代码就能明白了，不用多说。

//b before
//a after
inline int getX(long long b, long long a) {
  a -= b;
  for(int i = 1; i <= xlen; ++i) {
    if((15ll << ((xlen - i) << 2)) & a) {
      return i;
    }
  }
}
inline int getY(long long b, long long a) {
  int x = getX(b, a);
  return (a >> ((xlen - x) << 2)) & 15;
}
//unmap是一个逆向离散化的数组
inline int getArr(int b, int a) {
  return arr[getX(unmap[b], unmap[a])][getY(unmap[b], unmap[a])];
}

具体实现

由于我这么设的状态，所以逆向连边是肯定的了。

正常来说肯定是要拓扑排序了，但是我弱，考场上并没想到

所以我写了个SPFA。。。。

// luogu-judger-enable-o2 不开O2会80分
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>

template<typename T>
inline void input(T &var) {
  char ch = ' ';
  T ope = 1;
  while((ch < '0' || '9' < ch) && ch != '-') {
    ch = getchar();
  }
  if(ch == '-') {
    ope = -1;
    ch = getchar();
  }
  var = 0;
  while('0' <= ch && ch <= '9') {
    var = var * 10 + ch - '0';
    ch = getchar();
  }
  var *= ope;
}
template<typename T>
inline void output(T var) {
  if(var < 0) {
    putchar('-');
    var = -var;
  } else if(var == 0) {
    putchar('0');
    return;
  }
  if(var >= 10) {
    output(var / 10);
  }
  putchar(var % 10 + '0');
  return;
} 

struct Edge {
  Edge(int to, Edge *next) : to(to), next(next) {  }
  Edge *next;
  int to;
} *first[300000];

std::map<long long, int> map;
long long unmap[300000];
long long memery[300000][2];
int cnt = 0;
int xlen;
int ylen;
long long ans = 0;
int arr[15][15];

void init();
void build();
long long solve();

int main() {
  init();
  build();
  output(solve() + ans);
  return 0;
}

void getMap(int x, int last_y, long long res) {
  --x;
  map[res << ((xlen - x) << 2)] = ++cnt;
  unmap[cnt] = res << ((xlen - x) << 2);
  ++x;
  if(x > xlen) return;
  for(int y = 1; y <= last_y; ++y) {
    getMap(x + 1, y, (res << 4) | y);
  }
  return;
}

inline int getYByX(long long res, int x) {
  res >>= ((xlen - x) << 2);
  res &= 15;
  return res;
}

void init() {
  input(xlen);
  input(ylen);
  getMap(1, ylen, 0);
  for(int i = 1; i <= xlen; ++i) {
    for(int j = 1; j <= ylen; ++j) {
      input(arr[i][j]);
    }
  }
  int key;
  for(int i = 1; i <= xlen; ++i) {
    for(int j = 1; j <= ylen; ++j) {
      input(key);
      arr[i][j] += key;
      ans -= key;
    }
  }
  return;
}

inline void addEdge(int from, int to) {
  first[from] = new Edge(to, first[from]);
  return;
}

void build() {
  std::queue<long long> que;
  que.push(1ll << ((xlen - 1) << 2));
  static bool vis[300000];
  memset(vis, 0, sizeof(vis));
  vis[map[1ll << ((xlen - 1) << 2)]] = true;
  while(!que.empty()) {
    long long now = que.front();
    que.pop();
    if(getYByX(now, 1) < ylen) {
      long long next = now + (1ll << ((xlen - 1) << 2));
      //addEdge(map[now], map[next]);
      addEdge(map[next], map[now]);
      if(!vis[map[next]]) {
        que.push(next);
        vis[map[next]] = true;
      }
    }
    for(int i = 2; i <= xlen; ++i) {
      if(getYByX(now, i - 1) <= getYByX(now, i)) continue;//no <
      long long next = now + (1ll << ((xlen - i) << 2));
      //addEdge(map[now], map[next]);
      addEdge(map[next], map[now]);
      if(!vis[map[next]]) {
        que.push(next);
        vis[map[next]] = true;
      }
    }
  }
  return;
}

inline int getX(long long b, long long a) {
  a -= b;
  for(int i = 1; i <= xlen; ++i) {
    if((15ll << ((xlen - i) << 2)) & a) {
      return i;
    }
  }
}
inline int getY(long long b, long long a) {
  int x = getX(b, a);
  return (a >> ((xlen - x) << 2)) & 15;
}

inline int getArr(int b, int a) {
  return arr[getX(unmap[b], unmap[a])][getY(unmap[b], unmap[a])];
}

long long solve() {
  memset(memery, -1, sizeof(memery));
  addEdge(2, 1);
  long long fin = 0;
  for(int i = 1; i <= xlen; ++i) {
    fin <<= 4;
    fin |= ylen;
  }
  fin = map[fin];
  for(int i = 1; i <= cnt; ++i) {
    memery[i][0] = 0x7fffffffffffffff;
    memery[i][1] = 0x8000000000000000;
  }
  memery[fin][0] = memery[fin][1] = 0;

  std::queue<int> que;
  que.push((int)fin);
  static bool in_que[300000];
  memset(in_que, 0, sizeof(in_que));
  while(!que.empty()) {
    int now = que.front();
    que.pop();
    in_que[now] = false;
    for(Edge *edg = first[now]; edg != NULL; edg = edg->next) {
      bool flag = false;
      if(memery[now][1] < memery[edg->to][0]) {
        memery[edg->to][0] = memery[now][1];
        flag = true;
      }
      if(memery[edg->to][1] < memery[now][0] + getArr(edg->to, now)) {
        memery[edg->to][1] = memery[now][0] + getArr(edg->to, now);
        flag = true;
      }
      if(flag) {
        if(in_que[edg->to]) continue;
        in_que[edg->to] = true;
        que.push(edg->to);
      }
    }
  }
  return memery[1][1];
}