BZOJ3591 最长上升子序列

BZOJ

分析

$\color{black}{\mathrm{n}}\color{red}{\mathrm{zr}}$:一眼状压题。

考虑如何求 LIS ,发现设了一个数组 $lis_i$ 表示长度为 $i$ 的 LIS 末尾的数最小能是多少。

可以发现 $lis$ 数组是单调递增的,于是只要知道哪些数在里面就可以还原出整个数组。

考虑状压。对于每一个数有三种状态:没有考虑、考虑了而且在 $lis$ 数组中、考虑了但是不在 $lis$ 数组中。

于是可以三进制状压 DP 。转移直接枚举所有数然后插到最后去就好了。

具体实现和细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=16+10;
const int N3=14348907+10;

int n,m,ans=0;
int a[N],pos[N],pw[N];
int f[N3];
int state[N],seq[N];

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) a[i]=read()-1,pos[a[i]]=i;
    for (re int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*3;
    f[0]=1;
    for (re int i=0;i<pw[n];++i){
        if (!f[i]) continue;
        int cnt=0,top=0;
        for (re int j=0,s=i;j<n;++j) {
            state[j]=s%3,s/=3;
            if (state[j]) ++cnt;
            if (state[j]==1) seq[top++]=j;
        }
        if (cnt==n) { ans+=f[i]; continue; }
        for (re int j=0,p=0;j<n;++j) {
            if (state[j]) continue;
            if (pos[j]>1&&!state[a[pos[j]-1]]) continue;
            while (p<top&&seq[p]<j) ++p;
            if (p==m) continue;
            int nxt=i+pw[j]+(p<top?pw[seq[p]]:0);
            f[nxt]+=f[i];
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 20 PM

发表评论