「Luogu1108」 低价购买 - Dp

发表于 | 更新于: | 分类于 | | 阅读次数:

题目链接：传送门

Description

给定一个长为n(n<=5000)序列A，求最长下降子序列及方案数 ps：当二种方案“看起来一样”时（就是说它们构成的序列一样的时候）,这2种方案被认为是相同的。如:2,1,1,1,1中方案数为1

Solution

对于第一问，我们直接跑一遍n2n^2的LIS即可 对于第二问，我们记

TeX parse error: Undefined control sequence \[

表示到第i位，长度为

TeX parse error: Undefined control sequence \[

的LIS的个数， 那么有

TeX parse error: Undefined control sequence \[

对于判重，如果

TeX parse error: Undefined control sequence \[

&&

TeX parse error: Undefined control sequence \[

就说明这两种情况完全一样，所以对i位以前的j位进行清零。这样就能将cnt求出来了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
int n;
int a[maxn],f[maxn],cnt[maxn];
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int ans=0;
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]>a[i])
                f[i]=max(f[i],f[j]+1);
        ans=max(ans,f[i]);
    }
    printf("%d ",ans);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(a[j]>a[i] && f[i]==f[j]+1)
                cnt[i]+=cnt[j];
            if(a[j]==a[i] && f[i]==f[j])
                cnt[j]=0;
        }
        if(f[i]==1)cnt[i]=1;
    }
    int ans2=0;
    for(int i=1;i<=n;i++)
        if(ans==f[i])ans2+=cnt[i];
    cout<<ans2<<endl;
    return 0;
}
感谢你的赞赏!