锐客网

  1. 首页 > it技术 > >

题解|题解 最长上升序列2 — LIS2

最长上升序列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),
接下来,考虑状态转移.
【题解|题解 最长上升序列2 — LIS2】枚举\(t\)中的每个二进制位为1的数,并更新\(q\)(就是那个栈),
再搜索下一层,
当\(t\)等于0,即每个数都被选时,如果\(len\)等于\(k\),就返回1,
如果当前的\(s\)已经被搜过,就直接返回就行了.
还有什么不明白的就看代码吧:

#include #include #include #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

转载于:https://www.cnblogs.com/zsq259/p/10603882.html

    推荐阅读


    上一篇：在|在 eclipse 中调出其内置的浏览器

    下一篇：Fedora22编译Qt3.3.X