题目：https://www.luogu.org/problemnew/show/P4363
一种考虑状态数的方法：有几个用了k个格子的列，就在第k个0的左边插入几个1；
这也是求不降序列的个数的方法。本题中这样一看，一共有C(10,20)个状态。*m得出记忆化搜索的时间复杂度是18e6左右。
利用hash和map记忆化搜索。那个dg可以设成全局变量，每次复原一下，就不用专门解hash了。之所以还要记s是为了记忆化搜索作角标。
其实这个代码只能在bzoj上A，洛谷上会超时。不超时的方法似乎是轮廓线dp之类。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
const ll INF=2e8;
int n,m,tot,base,dg[];
ll a[][][];
map<ll,ll> dp;
map<ll,bool> vis;
ll pw(ll a,int ct)
{
ll ret=;
while(ct)
{
if(ct&)ret*=a;
a*=a;ct>>=;
}
return ret;
}
ll dfs(ll s,bool k)
{
if(vis[s])return dp[s];
vis[s]=;ll ret=-INF;
// ll ts=s;
// int dg[15]={0};
// for(int i=1;i<=m;i++)dg[i]=ts%base,ts/=base;
if(dg[m]==n)return ;
for(int i=;i<=m;i++)
if((i==&&dg[i]<n)||dg[i-]>dg[i])
{
dg[i]++;
ret=max(ret,a[k][dg[i]][i]-dfs(s+pw(base,i-),!k));
dg[i]--;
}
return dp[s]=ret;
}
int main()
{
scanf("%d%d",&n,&m);base=n+;
for(int k=;k<=;k++)for(int i=;i<=n;i++)for(int j=;j<=m;j++)scanf("%lld",&a[k][i][j]);
printf("%lld",dfs(,));
return ;
}