即求原序列最长下降子序列长度和满足最长的不同序列个数
f[i]表示以a[i]结尾的最长下降子序列长度,g[i]表示序列个数。
f[i]=max{$f[j]$}+1,其中j满足$a[j]>a[i]$,$1<=j<i$。
g[i]=$\sum\limits_{1<=j<i,a_j<a_i,f_j+1==f_i}^ng_j$,且需要注意,由于不同位置组成的相同子序列只计算一次,所以遇到a[j]相同的j时只累加一次,这里可以用一个map实现。
至此本题已经结束了,但是可以考虑这样一个优化:新建一个取值为负无穷的点a[n+1]并在DP时考虑进去,则最后答案就是f[n+1]-1和g[n+1],可以对代码长度进行一定缩减。
代码
#include<cstdio>
#include<map>
using namespace std;
const int N=5001;
int f[N],a[N],g[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=1,g[i]=1;
a[n+1]=-100000000;f[n+1]=1,g[n+1]=1;
for(int i=2;i<=n+1;i++){
map<int,int>mp;
for(int j=i-1;j>=1;j--){
if(a[j]<=a[i])continue;
if(f[j]+1==f[i]){if(!mp[a[j]])g[i]+=g[j],mp[a[j]]=1;}
else if(f[j]+1>f[i])f[i]=f[j]+1,g[i]=g[j],mp.clear(),mp[a[j]]=1;
}
}
printf("%d %d",f[n+1]-1,g[n+1]);
}