最长上升序列2 — LIS2
Description
已知一个 1 ∼ N 的排列的最长上升子序列长度为 K ，求合法的排列个数。
Input
输入一行二个整数 N , K ( K ≤ N ≤ 15) 。
Output
输出一行一个整数，描述合法的排列个数。
Sample Input
15 8
Sample Output
37558353900
解析
这题...额...还是得打记搜.
首先,让我们回顾一下求最长上升序列的二分的方法吧(神犇可自动跳过当然神犇可能不需要看本蒟蒻的题解)
我们维护一个类似于栈的数组(q)(其实是序列但为了方便懒得打字后面就称作栈吧)
令(q[i])表示长度为(i)的序列的最后一个元素,
那么,从(1)~(n)枚举,每次在(q)中寻找第一个大于(a[i])(即权值)的元素,
再用(a[i])去更新它,并且它的下标就是以(a[i])结尾的最长上升序列.
最后,再从(1)~(n)扫一遍,取最大值就行了.
那么,回到这题,
我们在搜索时,保留三个信息(s),(t),(len),
(s)表示栈中的信息,(t)表示每个数字是否被选中,(len)表示最长上升子序列,
并且,(s),(t)都可以状压,
对于(s),用一个三进制数表示,0表示未考虑,1表示已被更新,2表示目前在栈中,
对于(t),用二进制数表示就行了,0表示已选,1表示未选.
那么,初始状态就是(0,(1<<(n))-1,0),
接下来,考虑状态转移.
枚举(t)中的每个二进制位为1的数,并更新(q)(就是那个栈),
再搜索下一层,
当(t)等于0,即每个数都被选时,如果(len)等于(k),就返回1,
如果当前的(s)已经被搜过,就直接返回就行了.
还有什么不明白的就看代码吧:
#include <cstdio>
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
return f*sum;
}
int n,m;
ll f[15000001];
int a[1<<15]/*状态对应的数字*/,p[16]/*3的指数*/;
int q[10001]/*栈*/;
ll dfs(int s/*栈的状态*/,int t/*数字被选的状态*/,int len/*最长上升序列的长度*/){
if(!t) return len==m;//每个数都被选了
if(f[s]!=-1) return f[s];
f[s]=0;int pos=0,tt=t;
while(t){
int k=t&-t;t^=k;//用lowbit寻找二进制位为1的状态
while(pos<len&&q[pos+1]<a[k]) pos++;
int l=q[pos+1];
q[pos+1]=a[k];//寻找并更新栈
f[s]+=dfs(s+2*p[a[k]]-p[l],tt^k,len+(pos==len));
q[pos+1]=l;//回溯
}
return f[s];
}
int main(){
n=read();m=read();//m就是k,不过写习惯了[滑稽]
for(int i=1;i<=n;i++){
a[1<<(i-1)]=i;//预处理,状态所代表的数
p[i]= i==1? 1:p[i-1]*3;//三的指数
}
memset(f,0xff,sizeof(f));
printf("%lld
",dfs(0,(1<<n)-1,0));
return 0;
}