[题解][洛谷P1108] 低价购买

题目描述

求最长下降子序列长度，以及最长下降子序列的个数。
（构成的序列一样的时候，视为同一种最长下降子序列）

题解

n不超过5000，n^2复杂度即可解决该问题。
主要在于如何统计最长下降子序列个数。
可以设数组t[i]表示以i为结尾的最长下降子序列个数，在更新f[i]的时候顺便更新。
t[i]=sum(t[j]),当且仅当 a[j] > a[i] 且 f[i] = f[j]+1 。

代码

#include<bits/stdc++.h>
#define  int  long long
using namespace std;
const int N=5007;
int a[N],f[N],t[N];
signed main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i],t[i]=1,f[i]=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[j]>a[i]){if(f[i]==f[j]+1)t[i]+=t[j];else if(f[i]<f[j]+1)f[i]=f[j]+1,t[i]=t[j];}if(a[j]==a[i])f[j]=t[j]=0;//注意这里的去重操作}}int ans=1,cnt=0;for(int i=1;i<=n;i++){if(f[i]>ans){ans=f[i];cnt=t[i];}else if(f[i]==ans)cnt+=t[i];}cout<<ans<<" "<<cnt<<endl;
}