最长下降子序列O(n^2)及其方案数

直接贴代码，可以直接用
len是长度，ans是方案数

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 100005
using namespace std;
int a[5005],dp[5005];
ll num[5005];
int main(){
    int n;
    scanf("%d",&n);
    ll len=0;
    ll ans=0;
    a[0]=inf;
    dp[0]=0;
    num[0]=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=i-1;j>=0;j--){
            if(a[i]<a[j] and dp[i]<=dp[j])dp[i]=dp[j]+1;
        }
        for(int j=i-1;j>=0;j--){
            if(a[i]<a[j] and dp[i]==dp[j]+1)num[i]+=num[j];
            else if(a[i]==a[j] and dp[i]==dp[j])break;
        }
    }
    for(int i=1;i<=n;i++)if(len<dp[i]){len=dp[i];ans=num[i];}else if(len==dp[i])ans+=num[i];
    printf("%lld %lld",len,ans);
    return 0;
}
/*
 input
 12
 68 69 54 64 68 64 70 67
 78 62 98 87
 output
 4 2
 */

要求最长上升的话把数组倒着存就行