1108 低价购买

难度:提高+/省选-

题目类型:动规

提交次数:3(待定)

涉及知识:线性动规

题目描述

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

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

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

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

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

日期 2 5 6 10

价格 69 68 64 62

输入输出格式

输入格式:

第1行: N (1 <= N <= 5000),股票发行天数

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

输出格式:

输出文件仅一行包含两个数:最大购买次数和拥有最大购买次数的方案数(<=2^31)当二种方案“看起来一样”时(就是说它们构成的价格队列一样的时候),这2种方案被认为是相同的。

代码:(待修改!)

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[5005];
 5 int d[5005];//以a[i]结尾的最长LIS长度
 6 int g[5005];//以a[i]结尾的最长LIS方案数
 7 int n;
 8 int main(){
 9     int i, j;
10     int ans = 0;
11     cin>>n;
12     for(i = 0; i < n; i++){
13         scanf("%d", &a[i]);
14         d[i] = 1;
15         g[i] = 0;
16     }
17     for(i = 0; i < n; i++)
18         for(j = 0; j < i; j++){
19             if(a[j]>a[i])
20                 d[i] = max(d[i], d[j]+1);
21             ans = max(ans, d[i]);
22         }
23     printf("%d ", ans);
24     for(i = 0; i < n; i++){
25         for(j = 0; j < i; j++){
26             if(a[j]>a[i]&&d[j]+1==d[i]) g[i]+=g[j];
27         }
28         for(j = 0; j < i; j++){
29             if(a[j] == a[i] && d[i] == d[j]) g[j] = 0;
30         }
31         if(d[i] == 1) g[i] = 1;
32     }
33     int sum = 0;
34     for(i = 0; i < n; i++)
35         if(d[i] == ans) sum+=g[i];
36     printf("%d\n", sum);
37     return 0;
38 } 

备注:

这个代码是有问题的!!第二个测试点WA,最后一个测试点超时。。找不到问题,回头再改

先来说一下思路,看了很多不同的解答,参考了不同的阐述,谁让我在某些问题上理解能力比较差。。。

统计方案数加去重的处理方法:对于每一个a[i],先统计它的方案数(这时g[i]以前的都已经进行过去重工作了),所以如果a[j]>a[i],d[j]+1==d[i],就说明d[j]一步就能转移到d[i],那直接把g[i]累加到g[j]上就好了。

关键的是查重方法,即清零那部分比较谜。如果a[j] == a[i]并且d[i] == d[j],那么可以确定,这是完全重了的,因为j在前,方案数只能小于等于i,因此将j清零。这一点也许有点难理解。可以这么想,因为这个j循环是套在i循环里的,从LIS的第一个数开始,每一轮都会进行这个去重操作。看到有一位博主是这样阐述的:“……能转移到j上的一定也能转移到i上”。

好吧其实我自己还是没有那么清楚,待补充。每个人都可能有自己的困惑点,举举例子试一试是个好方法。

时间: 10-03

1108 低价购买的相关文章

洛谷1108 低价购买

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

洛谷P1108 低价购买[DP | LIS方案数]

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

入门动态规划 洛谷P1108 低价购买

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

动态规划---最长上升子序列问题(O(nlogn),O(n^2))

LIS(Longest Increasing Subsequence)最长上升子序列 或者 最长不下降子序列.很基础的题目,有两种算法,复杂度分别为O(n*logn)和O(n^2) . ********************************************************************************* 先回顾经典的O(n^2)的动态规划算法: 设a[t]表示序列中的第t个数,dp[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设dp[

TCL牵手美的,黑白跨界齐聚520

5月20日,不仅是年轻人的一个特殊日子,因为其谐音"我爱你",很多人会借助这一天,向身边的爱人.家人或朋友表达爱意.这么重要的一个日子,家电行业也不会放弃开展一场的促销活动,据TCL官方得知,TCL电视将联合美的空调举办"520家电黑白配"为爱放价大行动,此次TCL与美的的跨界牵手,将一次性为消费者解决电视与空调的两大购物需求,让这个夏天吹着空调看球赛. 线上线下钜惠520家电黑白配 作为全球电视品牌前三的TCL和长期高居一二级能效产品市场榜首的美的空调,两大品牌互

烧钱时代终结!O2O还能玩啥花样?

        最终的最终,饱受亏损.烧钱玩补贴等争议的美团还是追随滴滴/快的.赶集/58的步伐,与大众点评愉快的在一起了!美团和大众点评作为O2O行业的领军企业,都因为不堪忍受持续地投入却不见回报的模式而不得不放低姿态,采取合并的形式来降低成本,那对于中小型乃至初创020企业来说,更是在一定程度上证明烧钱大战不具备可持续性. 随着融资越来越难,以烧钱补贴换市场的做法越来越不可取.这种某种程度上违背市场经济运行.价值规律的非常规手段,将迅速成为过去式.简单.粗暴的烧钱时代终结,意味着O2O行业将

为什么选择美国空间

有些人可能会问:为什么要选择美国空间?国内有大把空间!确实,国内能够提供网站空间的空间商很多,其中不乏比较优秀的空间商!尽管如此,还是很多人选择了美国空间!我们不得不承认,美国是互联网的鼻祖,美国网络是目前世界上最发达的.美国空间在欧美地区打开的速度非常快,在全球范围内访问的速度都是不错的.而国内的空间存在不少弊端,比如网通跟电信互联不互通的问题,网站备案比较繁锁的问题,国外客户基本打不开国内空间的问题.这些问题对经营海外业务,想开拓海外市场的人很是不利. 那么美国空间对与国内用户来说有哪些优势

高性价比不等于低价,华为存储用“创新”赢用户

2015年伊始,很少在媒体面前露面的EMC全球高级副总裁.大中华区总裁叶成辉在谈到国内存储市场时,曾很有深意地说过一句话:"选价格华为胜,选技术EMC胜,输赢早知道".如此直接地选择一家同行厂商来比较,EMC给出言简意赅的评价,令人印象深刻.然而,立春刚过,就在2月6日,浙江电信与华为联合宣布,浙江电信基于华为FusionStorage软件定义存储(SDS)的IT基础设施正式投入商用,它承载着浙江电信的核心业务,表现稳定. 两件事情间隔如此之近,笔者不禁大胆猜测,极少回应友商评价的华为

国产低价手机低的是“专利” 谈何技术创新?

当下,国产手机厂商依然在玩着各种花样:玩情怀.玩文艺.玩外壳.玩材质.玩低价.玩营销--看似热闹异常,其实却隐患重重,问题多多.近日,国产手机厂商中的翘楚小米.联想等,就直接被高通"抄了后路".据知情人士透露,作为中国最大的两家智能手机厂商之一,小米和联想均未与高通签订最新的专利授权协议. 这意味着,小米.联想此前华丽的销售成绩或财报,都是建立在"赖账"的基础之上.对于利润贴地飞行的国产手机来说,专利费是它们永远绕不开的坎,为了能在残酷的市场竞争中先存活下来,只能选