题目传送门
https://www.lydsy.com/JudgeOnline/problem.php?id=5248
思路
显然每个局面，落子无悔后都是一个从上往下的非严格递减阶梯。
所以有效的状态数只有很少，每一行减下一行非负，方案数用隔板法随便一算发现是
Cnm+n
这么多，不到
2∗105
。所以用一个
(m+1)
进制数压一波，丢进map里哈希掉。
然后每一行只能放末尾，所以枚举一下，变成一个子问题倒着转移就算出答案。由于先后手需要分开讨论，分别取max或min，所以这个东西就是传说中的对抗搜索。
ps：这又是一道bzoj能过，洛谷TLE的题目。
代码
#include <bits/stdc++.h>
#define maxn 15
#define INF 0x7FFFFFFF
using namespace std;
typedef long long LL;
map <LL, int> M;
int n, m;
int A[maxn][maxn], B[maxn][maxn];
int num[maxn];
LL Zip(){
LL res =
0;
for(
int i =
1; i <= n; i++) res = res *
11 + num[i];
return res;
}
void UnZip(LL sta){
for(
int i = n; i >
0; i--){
num[i] = sta %
11;
sta /=
11;
}
}
int Get(){
LL res =
0;
for(
int i =
1; i <= n; i++)
res += num[i];
return !(res &
1);
}
int Dfs(LL sta){
if(M.count(sta))
return M[sta];
UnZip(sta);
int type = Get(), res = type ? -INF : INF;
for(
int i =
1; i <= n; i++)
if(num[i-
1] > num[i]){
num[i] ++;
if(type) res = max(res, Dfs(Zip())+A[i][num[i]]);
else res = min(res, Dfs(Zip())-B[i][num[i]]);
num[i] --;
}
return M[sta] = res;
}
int main(){
scanf(
"%d%d", &n, &m);
for(
int i =
1; i <= n; i++)
for(
int j =
1; j <= m; j++)
scanf(
"%d", &A[i][j]);
for(
int i =
1; i <= n; i++)
for(
int j =
1; j <= m; j++)
scanf(
"%d", &B[i][j]);
for(
int i =
0; i <= n; i++) num[i] = m;
M[Zip()] =
0;
printf(
"%d\n", Dfs(
0));
return 0;
}
