BZOJ3591 最长上升子序列

题意

给出$n$个数的一个排列的一个最长上升子序列,求原排列可能的种类数。
$1 \leqslant n \leqslant 15$。

题解

一道比较巧妙的DP,以前觉得复杂度$O(3^n)$级别的状压DP就只能枚举子集了,原来还可以这么搞= =。
考虑我们在$O(n\log n)$复杂度内是怎么把LIS求出来的。大概就是二分一个位置。如果这个位置在序列末位,就加上这个数,否则用新来的数替换掉二分到的位置上的那个数。于是我们可以想到一个这样的状压DP。对于每个数,有三个状态:0表示这个数还没有被选到集合中,1表示已经被选到集合中,且存在于LIS中,2表示已经被选在集合中,但已不再LIS中,转移也就十分显然了。其实可以从小到大枚举新加的数,这样用一个指针扫一遍,就可以去掉二分的那个$\log n$。
时间复杂度$O(3^nn)$,BZOJ上总时限2000ms……比较卡常数……需要加一些剪枝。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=15+5;
const int maxsz=15000000+10;
int a[maxn],pre[maxn],dp[maxsz],Pow[maxn],val[maxn],num[maxn],LIS[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline int max(int A,int B){
return A>B?A:B;
}
int main(){
int n,m;
n=read();m=read();
for(register int i=1;i<=m;i++)a[i]=read(),pre[a[i]]=a[i-1];
Pow[0]=1;for(register int i=1;i<=n;i++)Pow[i]=Pow[i-1]*3;
dp[0]=1;
int ans=0;
for(register int i=0;i<Pow[n];i++){
if(!dp[i])continue;
int id=i,cnt1=0,cnt2=0;
for(register int j=1;j<=n;j++){
val[j]=id%3;
if(val[j]==0)num[++cnt1]=j;
if(val[j]==1)LIS[++cnt2]=j;
id/=3;
}
if(cnt2>m)continue;
if(cnt2<=m && cnt1==0){
ans+=dp[i];
continue;
}
int pos=1;
for(register int j=1;j<=cnt1;j++){
int Dp=i;
if(pre[num[j]] && !val[pre[num[j]]])continue;
while(num[j]>LIS[pos] && pos<=cnt2)pos++;
if(pos<=cnt2)Dp+=Pow[max(0,LIS[pos]-1)];
Dp+=Pow[num[j]-1];
dp[Dp]+=dp[i];
}
}
printf("%d\n",ans);
return 0;
}