洛谷 1108 低价购买

本文主要是介绍洛谷 1108 低价购买，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://www.luogu.org/problem/show?pid=1108#
第一问就是裸的最长下降子序列
第二问比较难，看了题解想了好久才明白，可以加一个t[i]数组表示1到i取最长下降子序列的方案数，显然如果f[i]==1则t[i]=1，然后j从1到i-1循环，f[i]==f[j]+1&&a[i]< a[j]时说明可以从1到j的最长子序列后加一个a[i]即加上t[j]个方案数，这里要去除“看起来一样”的方案，当f[i]==f[j]&&a[i]==a[j]时，f[j]即重复的，直接t[j]=0。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[5010],a[5010],t[5010];
int n,ans1,ans2;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=i-1;j++){if(a[i]<a[j])f[i]=max(f[i],f[j]+1);}if(f[i]==1)t[i]=1;for(int j=1;j<=i-1;j++){if(f[i]==f[j]+1&&a[i]<a[j])t[i]+=t[j];if(f[i]==f[j]&&a[i]==a[j])t[j]=0;}}for(int i=1;i<=n;i++)ans1=max(f[i],ans1);for(int i=1;i<=n;i++)if(f[i]==ans1)ans2+=t[i];printf("%d %d",ans1,ans2);return 0;
}

这篇关于洛谷 1108 低价购买的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---