「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;
}
感谢你的赞赏!