https://www.luogu.org/problem/show?pid=1108#sub
第一问，求一个最长的下降子序列就可以了。 难点在于第二问，解决方法： 设f[i]表示到i这一位置，最长下降子序列的最大方案数； 当构成序列相同时，可以看出……呃，举个例子吧： 股票价格为：4 ， 2 ， 2 ， 3 ， 1 最长的下降子序列为：4 2 1 或 4 2 1 或4 3 1 ，有两种是相同的，可以判断出数字2，用后面的就包括前面的了。 那么 , f[i]=Σf[j],( 0< j< i 且d[j]=d[i]-1且a[j]不重复) 处理时，就可以在处理出f[i]后，把前面的f[j]==f[i]的f[j]改为0就可以了。 ！！而且，当且仅当d[i]=1时,f[i]=1！！切记！
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int d[5009],f[5009]; int n,a[5009],m1,m2; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); d[i]=1; } d[n+1]=1;f[1]=1; for(int i=2;i<=n+1;i++) { int maxn=0; for(int j=1;j<=i-1;j++) { if(a[j]>a[i]&&d[j]>maxn) maxn=d[j]; } d[i]+=maxn; if(d[i]==1) f[i]=1; for(int j=1;j<=i-1;j++) { if(a[i]==a[j]) f[j]=0; if(d[j]==d[i]-1&&a[i]<a[j]) f[i]+=f[j]; } } printf("%d %d",d[n+1]-1,f[n+1]); return 0; }