洛谷 P1108 低价购买(LIS,统计方案数)

传送门


解题思路

看第一个要求,很显然是求最长下降子序列,和LIS几乎一样,很简单,再看第二个问号,求最长下降子序列的方案数??这怎么求?

注意:当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。

这里就用到了一种基于dp的dp。

我们用a[i]存原来的数,f[i]存以第i个数结尾的最长下降子序列的长度,t[i]存以i结尾的最长下降子序列的方案数。

f[i]照常求,那么t[i]不能重复,怎么求呢?

首先,对于每一个i,枚举j=1...i-1。

  • 若f[i]==f[j]且a[i]==a[j],这时f[i]的方案数是>=f[j]的,因为题目要求不能重复,所以我们把较小的那个t[j]定为0,t[i]不变,继续求。
  • 若f[i]=f[j]+1且a[i]<a[j],也就是说f[j]这个序列的最后可以加上a[i]这个数,所以这时t[i]+=t[j],继承过t[i]的方案数。

最后,如果t[i]还是等于0,那么代表着a[i]不能成为任何一个序列的最后一个数,说明a[i]是到目前为止的最大的数,这时t[i]赋值为1。

最后统计出答案即可。

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn=5005;
 5 int a[maxn],f[maxn],t[maxn];
 6 //a[i]存原来的数,f[i]存以第i个数结尾的最长下降子序列的长度,
 7 //t[i]存以i结尾的最长下降子序列的方案数
 8 int n,maxf;
 9 long long ans; 
10 int main()
11 {
12     cin>>n;
13     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
14     for(int i=1;i<=n;i++){
15         for(int j=1;j<i;j++){
16             if(a[i]<a[j]) f[i]=max(f[i],f[j]+1);
17         }
18         if(f[i]==0) f[i]=1;
19         maxf=max(maxf,f[i]);
20         for(int j=1;j<i;j++){
21             if(f[i]==f[j]&&a[i]==a[j]){
22                 t[j]=0;
23             }
24             if(f[i]==f[j]+1&&a[i]<a[j]){
25                 t[i]+=t[j];
26             }
27         }
28         if(t[i]==0) t[i]=1;
29     }
30     for(int i=1;i<=n;i++){
31         if(f[i]==maxf) ans+=t[i];
32     }
33     cout<<maxf<<" "<<ans;
34     return 0;
35 }

 

上一篇:公司项目启动的时候连接数据库问题


下一篇:XHXJ's LIS