传送门
解题思路
看第一个要求,很显然是求最长下降子序列,和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 }