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

低价购买

编程语言 qq_35914587 16℃ 0评论

QAQ


想一下思路


其实第一问挺简单的,就是求一个最大下降子序列


至于第二问我有点懵


拥有最大购买次数的方案数(<=2^31)


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


这个咋做呢


想一下


我们先处理出down[i]的每个值


枚举1-i,然后枚举1-i-1


如果down[i]==down[j]+1的话,那么j就是i的前驱


用t[i]为到i的方案是,如果满足上面的条件,那么,t[i]+=t[j]


如果a[i]==a[j]那么我们就得把,t[i]赋值为0,因为用后面的没有用前面的优


t[i]得赋初值为1,因为起码有一种方案

#include  
#include 
using namespace std;
int c[19999];
int down[9999];
int t[9999];
int main()
{
    int n;
    scanf("%d",&n);


    for(int i=1;i<=n;i++)
     scanf("%d",c+i);

    c[n+1]=-1;
    down[1]=1; 
    t[1]=1;
    for(int i=2;i<=n+1;i++)
     {
        int maxf=0;

        for(int j=1;jif(c[j]>c[i]) maxf=max(down[j],maxf);

        down[i]=++maxf;
        if(down[i]==1) t[i]=1;

        for(int j=1;jif(c[i]==c[j])
            t[i]=0;
          if(c[i]1)
           t[i]+=t[j];
        }

     }

     printf("%d %d",down[n+1]-1,t[n+1]);

     return 0;
}

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

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

*

表情