P1108 低价购买(DP)

题目描述

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2162^{16}216范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单:

日期 1,2,3,4,5,6,7,8,9,10,11,12 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8, 9 ,10 ,11, 121,2,3,4,5,6,7,8,9,10,11,12

价格68,69,54,64,68,64,70,67,78,62,98,87 68 ,69 ,54, 64,68 ,64 ,70 ,67 ,78 ,62, 98, 8768,69,54,64,68,64,70,67,78,62,98,87

最优秀的投资者可以购买最多444次股票,可行方案中的一种是:

日期 2,5,6,10 2 , 5 , 6 ,102,5,6,10

价格 69,68,64,62 69, 68 ,64 ,6269,68,64,62

输入输出格式

输入格式:

 

第1行: N(1≤N≤5000)N(1 \le N \le 5000)N(1≤N≤5000),股票发行天数

第2行: NNN个数,是每天的股票价格。

 

输出格式:

 

两个数:
最大购买次数和拥有最大购买次数的方案数(≤231 \le 2^{31}≤231)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这222种方案被认为是相同的。

 

输入输出样例

输入样例#1: 复制
12
68 69 54 64 68 64 70 67 78 62 98 87
输出样例#1: 复制
4 2

题解:

注意这不是LIS,因为它还要求出来方案数,而LIS的DP数组里面只是求出来了以dp[i]以第i个数结尾的LIS,而且这道题还要求我们去重<_>

 

因此我参考了一下别人的博客https://wjyyy.blog.luogu.org/solution-p1108

  1. 如果一个数列的第一个数与另一个数列的第一个数相同,那么现在可以判断它们相等,即可以把其中一个删掉(在代码中的处理是t[i]=0t[i]=0t[i]=0)。当不同的数接在它的后面时,又可以将它们判断为两个数列,这是不互相影响的。因为两个数列都可以由这个相等的数列转移而来
  2. 如果一个数列的第一个数与另一个数列的第一个数不同,那么它们不等,且无论后面添加什么,都不相等,即不删去,则按照普通的判断继续做。

由上面的两点,我们已经把重复的删掉,这样可以防止重复计数

tiptiptip:本题如果出现在考试中,请不要冒险定义int,因为maxint是231−12^{31}-1231−1,会爆int,这个题暂不做深究

 

上代码:

P1108 低价购买(DP)
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=1000005;
 7 int v[maxn],dp[maxn],t[maxn];
 8 int main()
 9 {
10     int n,m,maxx=0;
11     scanf("%d",&n);
12     m=n;
13     for(int i=1;i<=n;++i)
14         scanf("%d",&v[m--]);
15     for(int i=1;i<=n;++i)
16     {
17         dp[i]=1;
18         for(int j=1;j<i;++j)
19         {
20             if(v[j]<v[i] && dp[j]+1>dp[i])
21                 dp[i]=dp[j]+1;
22         }
23         maxx=max(maxx,dp[i]);
24 
25         for(int j=1;j<i;++j)
26         {
27             if(dp[j]==dp[i] && v[j]==v[i])
28                 t[j]=0;
29             else if(dp[j]+1==dp[i] && v[j]<v[i])
30                 t[i]+=t[j];
31         }
32         if(!t[i]) t[i]=1;
33     }
34     int sum=0;
35     for(int i=1;i<=n;++i)
36     {
37         if(dp[i]==maxx)
38             sum+=t[i];
39     }
40     printf("%d %d\n",maxx,sum);
41 }
View Code

 

上一篇:MySQL创建数据库并且插入数据


下一篇:购物车程序