原题链接
d[i]是以 i 这个位置结束的最长下降子序列的长度
第一问就是求个最长下降子序列
第二问 记录以 i 这个位置结束 长度为d[i]的下降子序列的方案总数 d[i]=d[j]+1（1<=j < i）的 j 的方案数相加 但是当两个不同的位置上存的数相同且均满足上式时 就会产生重复 因为位置靠后的数肯定包含了位置靠前的数所有的方案 所以只保留位置靠后的方案数
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MOD 10007 #define LL long long using namespace std; int n,i,j,cost[5005],down[5005],solu[5005],ans1,ans2; int main() { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&cost[i]); down[i]=1; } for(i=1;i<=n+1;i++) { for(j=1;j<i;j++) if(cost[i]<cost[j]) down[i]=max(down[i],down[j]+1); if(down[i]==1) solu[i]=1; for(j=1;j<i;j++) { if(cost[i]==cost[j]) solu[j]=0; if(cost[i]<cost[j]) if(down[i]==down[j]+1) solu[i]+=solu[j]; } } ans1=down[n+1]-1; ans2=solu[n+1]; printf("%d %d",ans1,ans2); return 0; }