即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

P1108 低价购买dp

编程语言 qq_36820605 19℃ 0评论

https://www.luogu.org/problem/show?pid=1108#sub


这里写图片描述

第一问,求一个最长的下降子序列就可以了。


难点在于第二问,解决方法:


设f[i]表示到i这一位置,最长下降子序列的最大方案数;


当构成序列相同时,可以看出……呃,举个例子吧:


股票价格为:4 , 2 , 2 , 3 , 1


最长的下降子序列为:4 2 1 或 4 2 1 或4 3 1 ,有两种是相同的,可以判断出数字2,用后面的就包括前面的了。


那么 , f[i]=Σf[j],( 0< j< i 且d[j]=d[i]-1且a[j]不重复)


处理时,就可以在处理出f[i]后,把前面的f[j]==f[i]的f[j]改为0就可以了。


!!而且,当且仅当d[i]=1时,f[i]=1!!切记!

代码

#include
#include
#include
#include
using namespace std;
int d[5009],f[5009];
int n,a[5009],m1,m2;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        d[i]=1;
    }
    d[n+1]=1;f[1]=1;    
    for(int i=2;i<=n+1;i++)
    {
        int maxn=0;
        for(int j=1;j<=i-1;j++)
        {
            if(a[j]>a[i]&&d[j]>maxn)
             maxn=d[j];
        }
        d[i]+=maxn;
        if(d[i]==1) f[i]=1; 
        for(int j=1;j<=i-1;j++)
        {
            if(a[i]==a[j])
             f[j]=0;
            if(d[j]==d[i]-1&&a[i]printf("%d %d",d[n+1]-1,f[n+1]);
    return 0;
}

转载请注明:CodingBlog » P1108 低价购买dp

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情