原题：
n<=5000
第一个子问题是求最长下降子序列的长度，这个大家都会，用一个单调的g数组+二分可以nlogn求
第二个子问题是求本质不同的方案数
其实数据只有5000，可以用n^2来实现第一个子问题，完全没必要局限于nlogn的做法
研究本质相同的方案的特点
a表示输入的价格序列，g[i]和g[j]表示a[i]或a[j]结尾的方案数
如果j>i且a[j]==a[i]，那么g[j]一定>=g[i]
因为a[i]结尾的所有序列都可以继承到a[j]，而i和j中间可能还给a[j]提供了更多方案
前一部分是本质相同的方案数，因此可以直接无视a[i]而使a[j]给后续状态转移
这个很容易n^2处理，里层循环从右往左枚举，只统计每个价格第一次出现时的方案数
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,a[5100]; 5 int f[5100]; 6 bool u[110000]; 7 long long g[5100]; 8 int main(){ 9 cin>>n; 10 for(int i=1;i<=n;++i) scanf("%d",&a[i]); 11 for(int i=1;i<=n+1;++i){ 12 f[i]=1; 13 for(int j=i-1;j>=1;--j)if(a[j]>a[i]) 14 f[i]=max(f[i],f[j]+1); 15 for(int j=i-1;j>=1;--j)if(a[j]>a[i] && f[j]==f[i]-1 && !u[a[j]]){ 16 u[a[j]]=true; 17 g[i]+=g[j]; 18 } 19 if(f[i]==1) g[i]=1; 20 for(int j=i-1;j>=1;--j)if(u[a[j]]) u[a[j]]=false; 21 } 22 cout<<f[n+1]-1<<" "<<g[n+1]<<endl; 23 return 0; 24 }
原文：https://www.cnblogs.com/cdcq/p/12283499.html
