分析：这题要求满足最长下降子序列的个数，我们设dp[i]为i位置的最长下降子序列长度，f[i]为i位置对应的个数。考虑j<i,若是满足a[i]==a[j]&&dp[i]==dp[j]，我们应该进行去重，这时我们应取后一个位置，因为无论如何，后一个位置所取得的最长下降子序列的长度都不小于前一个位置。若是dp[i]-1==dp[j]&&a[j]>a[i]，这时f[i]=f[i]+f[j],因为此时i位置的个数，必定是所有j位置的和。这个递推是本题的难点
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 using namespace std; 6 const int maxn=5000+50; 7 int dp[maxn],f[maxn],a[maxn]; 8 int n; 9 int main() 10 { 11 cin>>n; 12 for(int i=0;i<n;i++) 13 cin>>a[i]; 14 for(int i=0;i<n;i++){ 15 dp[i]=1; 16 for(int j=0;j<i;j++){ 17 if(a[j]>a[i]&&dp[i]<dp[j]+1) 18 dp[i]=dp[j]+1; 19 } 20 } 21 int ans=0; 22 for(int i=0;i<n;i++) 23 ans=max(dp[i],ans); 24 for(int i=0;i<n;i++) 25 if(dp[i]==1) 26 f[i]=1; 27 for(int i=0;i<n;i++){ 28 for(int j=0;j<i;j++){ 29 if(dp[i]==dp[j]&&a[i]==a[j]) 30 f[j]=0; 31 else if(dp[i]-1==dp[j]&&a[j]>a[i]) 32 f[i]+=f[j]; 33 } 34 } 35 int cnt=0; 36 for(int i=0;i<n;i++) 37 if(dp[i]==ans) 38 cnt+=f[i]; 39 cout<<ans<<" "<<cnt<<endl; 40 return 0; 41 }