给出一个元素不重复，长为n<=15的序列的最长上升子序列之一。 求有多少个序列满足有这个最长上升子序列。
这tm也是一题玄学题。
因为n=15，考虑状压，dp. 一个序列只要满足两个条件就是合法序列： 1)最长上升子序列长度为k，2)子序列存在于原序列中。
第二个好求，直接状压。
问题是第一个。 因为我们要求最长上升子序列的长度，所以状态里要带一个dp时的f数组 这样超时。 想一想求最长上升子序列的n log n算法，我们发现只需要存一个长度为i的上升子序列的最小结尾元素 也就是“辅助栈”就可以更新序列最长上升子序列的长度了。
但是怎么存？ 因为辅助栈是单调的，所以只需要知道每个数有没有在辅助栈里出现就好了。 于是我们状态就有了，一个三进制的压位状态。 0表示没有出现过，1表示出现过，2表示出现过并且在辅助栈内。
转移比较显然，但需要加几个优化。 1）转移时注意到，因为x从小到大枚举，所以更新指针也会往前指。复杂度是O(n)的 2）找一下合法的一个必要条件优化： 因为a[i]是最长上升子序列中第i位，所以他前面不应该存在一个数x使得x<=a[i]且f[x]>=i.
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #define N 16 using namespace std; int f[14348908]; int n,k,a[N],g[N],app[N],t,su[N]; int m[N],ans,stm; void dfs(int x,int cnt,int st) { if (x>n) { if (f[st]==0) return; ++stm; g[0]=0; int s=st,nst=0,now=0; for (int i=1; i<=n; i++) { int yss=s/3,ys=s-yss*3; if (ys!=0) app[i]=stm; if (ys==2) g[++g[0]]=i; s=yss; if (s==0) break; } for (int x=1; x<=n; x++) if (app[x]!=stm) { if (su[x]>1 && app[a[ su[x]-1 ]]!=stm) continue; while (now<g[0] && g[now+1]<x) now++; bool bz=0; for (int i=1; i<=k; i++) if (app[a[i]]!=stm && a[i]>x && now+1>=i) { bz=1; break; } if (bz==1) continue; if (now==0 && g[1]<now) nst=st+m[x]; //0->1 else if (now!=g[0]) { nst=st+m[x]*2; //0->2 nst=nst - m[g[now+1]]; //2->1 } else nst=st+m[x]*2;//0->2 f[nst]+=f[st]; if (t==n-1 && g[0]+(now==g[0])==k) ans=ans+f[st]; } return; } if (n-x+1>t-cnt) dfs(x+1,cnt,st*3); if (cnt<t) { dfs(x+1,cnt+1,st*3+1); dfs(x+1,cnt+1,st*3+2); } } int main() { freopen("sword.in","r",stdin); freopen("sword.out","w",stdout); cin>>n>>k; m[1]=1; for (int i=2; i<=n; i++) m[i]=m[i-1]*3; for (int i=1; i<=k; i++) scanf("%d",&a[i]),su[a[i]]=i; if (k==1) { cout<<1<<endl; return 0; } f[0]=1; for (t=0; t<n; t++) dfs(1,0,0); cout<<ans<<endl; }