P1108 低价购买

题面:https://www.luogu.org/problemnew/show/P1108

本题首先是求一个最长下降子序列的问题,但难点是要去重。
其实也很简单,即当f[i]==f[j]且a[i]==a[j]，则f[j]就完全包含在f[i]中了,那么f[j]的方案数就无需累加了。

Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=5005;
int a[N],f[N],t[N];
int n,maxn,sum;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        f[i]=1;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[i]<a[j]){
                f[i]=max(f[i],f[j]+1);
            }
        }
        maxn=max(maxn,f[i]);
        for(int j=1;j<i;j++){
            if(f[i]==f[j]&&a[i]==a[j]){
                t[j]=0;
            }
            else if(f[i]==f[j]+1&&a[i]<a[j]){
                t[i]+=t[j];
            }
        }
        if(!t[i]){
            t[i]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(f[i]==maxn){
            sum+=t[i];
        }
    }
    printf("%d %d",maxn,sum);
    return 0;
}