bzoj5248(洛谷4363)(2018九省联考)一双木棋

题目：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 ;

}