给出一个长度为 m 的序列 A, 请你求出有多少种 1...n 的排列, 满足 A 是它的一个 LIS.
dp套dp好题！
我们先要考虑怎么搞一个状态出来
考虑做lis的两种方法：
1.设f[i]表示做到i的最长子序列长度
2.设f[i]表示长度为i的上升子序列最后那个数最小是多少
第一种方式不好设状态，我们考虑第二种
显然，如果知道f里有哪些数字，就可以还原f
那么我们设一个状态f[S][F]表示现在原来的序列中已经用了S这些数字，f数组中的数为F的方案数
考虑转移，显然有2种方式：
1.向S中添加一个不在A中的元素，这种情况直接转就可以了
2.向S中添加一个在A中的元素，这个时候要考虑顺序，如果A[1..j]都在F中出现过，那么我们可以添加的元素就是A[j+1]
最后答案就是∑ f[S][F] 其中S为全集，F的集合大小为A的长度
这样不能满分，考虑简化状态，由于F∈ S，所以这个状态可以用3进制表示，这样就可以通过了
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int d3[20]={1},ans=0;
int n,m,v[20],g[20],p[20],s[20],f[20000000];
inline void cal(int i,int& j,int& k){
for(j=k=0;i;i/=3){
if(i%3==1) ++j; else
if(i%3==2) ++k;
}
}
int main(){
freopen("arg.in","r",stdin);
freopen("arg.out","w",stdout);
scanf("%d%d",&n,&m); *f=1;
for(int i=0;i<m;++i) scanf("%d",v+i),p[--v[i]]=i+1;
for(int i=1;i<=n;++i) d3[i]=d3[i-1]*3;
for(int i=0,k;i<d3[n];++i) if(f[i]){
for(int j=*g=k=0;j<n;++j){
s[j]=(i/d3[j])%3;
if(s[j]==1) g[++*g]=j;
if(s[j]) k=max(k,p[j]);
}
for(int j=0,t=1;j<n;++j) if(!s[j]){
while(j>g[t] && t<=*g) ++t;
if(p[j] && p[j]!=k+1) continue;
if(t<=*g) f[i+d3[j]+d3[g[t]]]+=f[i];
else f[i+d3[j]]+=f[i];
}
}
for(int i=0,j,k;i<d3[n];++i){
cal(i,j,k);
if(j==m && j+k==n){
ans+=f[i]; end:;
}
}
printf("%d
",ans);
}