这题在求最长下降子序列的基础上加了一个求方案数的要求,这就让这道题目变难了很多。
我们考虑我们在求最长下降子序列的时候,总是从这一位,要么重新开始计数,要么只和前面的有关,所以前面的信息完全丢失了,无法判断有多少方案,所以我们就要针对前面的方案数设计一个dp来统计。
可以称之为dp套dp?
其实我们不难想到,对于方案数也具有最优子结构,也无后效性,可以转移。
我们很自然地想到对于每一个可能的转移点,如果这个转移点是当前最优的,那么我们就要将方案数改成它;如果相等,则累加。
但是这样会有问题,即当相等时会让后面的点向前扫的时候重复计数,所以我们直接选择将其中一个的方案数变为0。
这道题就启示我们不要被一些看起来不是很好想的唬到了,其实还是很好想的。
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[5005],dp[5005],f[5005];
int main(){
scanf("%d",&n);
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]) dp[i]=max(dp[i],dp[j]+1);
}
if(!dp[i]) ++dp[i];
for(int j=1;j<i;++j){
if(dp[i]==dp[j]&&a[i]==a[j]) f[j]=0;
if(dp[i]==dp[j]+1&&a[i]<a[j]) f[i]+=f[j];
}
if(!f[i]) f[i]=1;
}
long long maxi=0,num=0;
for(int i=1;i<=n;++i) maxi=max(maxi,dp[i]);
for(int j=1;j<=n;++j){
if(dp[j]==maxi) num+=f[j];
}
printf("%lld %lld",maxi,num);
return 0;
}
标签:方案,5005,int,题解,P1108,我们,dp,低价
From: https://www.cnblogs.com/mountzhu/p/18421477