一句话题意：两个序列的LIS的长度和方案数
首先这里n方的应该是要比nlog的好的，因为还涉及到一个求方案
主要考虑下第二问， 不同的方案数应该怎么求
实际上 对于一个长为len的子序列，
它的方案数即为所有长为len-1的，且可以转移到它的子序列 （都是满足题意的）的方案数之和
这样就比较好办了，直接在原本的求LIS的转移里搞搞就行了。
那么答案就是所有长度为LIS的方案数之和了。
但是还有一个问题，这样的话根本没考虑方案是否重复。
那么怎么样把相同的去掉呢？？
我们把长度相等，当前对应位上的数也相等的，就先暂定为相等，删掉其中一个。
因为如果他们之前的也相同， 那么我们是可以直接全转移到当前的，删掉之前的。
如果之前的不相等， 那么之后它们的后面接上一个不同的数时，再作为两个判断就行了，互不影响。
贴下代码
#include<bits/stdc++.h> using namespace std; inline int gi() { int x=0,w=0;char ch=0; while(!(ch>=‘0‘&&ch<=‘9‘)) { if(ch==‘-‘) w=1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); return w?-x:x; } int n,post[5001],tot[5001],maxn,times[5001]; long long ans; int main() { n=gi(); for(int i=1;i<=n;i++) { post[i]=gi(); tot[i]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) if(post[i]<post[j]) tot[i]=max(tot[i],tot[j]+1); if(tot[i]>maxn) maxn=tot[i]; for(int j=1;j<i;j++) { if(tot[i]==tot[j]&&post[i]==post[j]) times[j]=0; else if(tot[i]==tot[j]+1&&post[i]<post[j]) times[i]+=times[j]; } if(!times[i]) times[i]=1; } for(int i=1;i<=n;i++) if(tot[i]==maxn) ans+=times[i]; printf("%d %d",maxn,ans); return 0; }
原文：https://www.cnblogs.com/Bhllx/p/9807189.html