看第一个要求，很显然是求最长下降子序列，和LIS几乎一样，很简单，再看第二个问号，求最长下降子序列的方案数？？这怎么求？
注意：当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。
这里就用到了一种基于dp的dp。
我们用a[i]存原来的数，f[i]存以第i个数结尾的最长下降子序列的长度,t[i]存以i结尾的最长下降子序列的方案数。
f[i]照常求，那么t[i]不能重复，怎么求呢？
首先，对于每一个i，枚举j=1...i-1。
最后，如果t[i]还是等于0，那么代表着a[i]不能成为任何一个序列的最后一个数，说明a[i]是到目前为止的最大的数，这时t[i]赋值为1。
最后统计出答案即可。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn=5005; 5 int a[maxn],f[maxn],t[maxn]; 6 //a[i]存原来的数，f[i]存以第i个数结尾的最长下降子序列的长度, 7 //t[i]存以i结尾的最长下降子序列的方案数 8 int n,maxf; 9 long long ans; 10 int main() 11 { 12 cin>>n; 13 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 14 for(int i=1;i<=n;i++){ 15 for(int j=1;j<i;j++){ 16 if(a[i]<a[j]) f[i]=max(f[i],f[j]+1); 17 } 18 if(f[i]==0) f[i]=1; 19 maxf=max(maxf,f[i]); 20 for(int j=1;j<i;j++){ 21 if(f[i]==f[j]&&a[i]==a[j]){ 22 t[j]=0; 23 } 24 if(f[i]==f[j]+1&&a[i]<a[j]){ 25 t[i]+=t[j]; 26 } 27 } 28 if(t[i]==0) t[i]=1; 29 } 30 for(int i=1;i<=n;i++){ 31 if(f[i]==maxf) ans+=t[i]; 32 } 33 cout<<maxf<<" "<<ans; 34 return 0; 35 }
原文：https://www.cnblogs.com/yinyuqin/p/11674469.html