[关闭]
@fuheimao 2015-09-25T13:01:28.000000Z 字数 1742 阅读 49

Buy low buy lower

NOIP 腹黑猫


【问题描述】
“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀:"逢低吸纳,越低越买"这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好,看看你最多能按这个规则买几次。
给定连续的N天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次购买时的股价低。写一个程序,求出最多能买几次股票。
以下面这个表为例, 某几天的股价是:
天数: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
【输入文件】buylow.in
第1行: N (1 N 5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ,第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++).
【输出文件】buylow.out
只有一行,输出两个整数:
能够买进股票的天数 长度达到这个值的股票购买方案数量
在计算解的数量的时候,如果两个解所组成的字符串相同,那么这样的两个解被认为是相同的(只能算做一个解)。因此,两个不同的购买方案可能产生同一个字符串,这样只能计算一次。
【输入样例】
12
68 69 54 64 68 64 70 67
78 62 98 87
【输出样例】
4 2
【题目分析】
price[i]为第i天的股票价格,length[i]为到i为止的最长下降子序列,solution[i]为到此位置为止的以price[i]结尾的最长下降子序列的个数(即方案数量)。
第一问中,能购买股票的天数,就是最长下降子序列。
第二问中,如何去掉重复方案,是这道题的关键之处。
当price[i] < price[j] && length[i] ==length[j]+1时,那以price[j]结尾的子序列一定被包含在以price[i]结尾的子序列中。
接下来就是如何去重。
例如price={5,3,2,1,3},当循环到最后一个solution[5]时,发现price[5]=price[2],那就把solution[2]清零,因为在后面出现的以3结尾的子序列一定会包含在前面出现的以3结尾的子序列。
【代码】(貌似需要高精度但是没写)

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int main(){
  5. int Price[5001] = {0}, Solution[5001] = {0}, Length[5001] = {0};
  6. int n;
  7. int MaxLength = -1;
  8. cin >> n;
  9. for (int i = 1; i <= n; i++){
  10. cin >> Price[i];
  11. }
  12. Length[1] = 1;
  13. Solution[1] = 1;
  14. for (int i = 2; i <= n; i++){
  15. //求最长下降子序列
  16. for (int j = i - 1; j >= 1; j--){
  17. if (Price[i] < Price[j] && Length[i] < Length[j]){
  18. Length[i] = Length[j];
  19. }
  20. }
  21. Length[i]++;
  22. MaxLength = Max(MaxLength, Length[i]);
  23. //求方案数
  24. if (Length[i] == 1){
  25. Solution[i] = 1;
  26. }else{
  27. for (int j = 1; j < i; j++){
  28. if (Price[j] > Price[i] && Length[i] == Length[j] + 1){
  29. Solution[i] += Solution[j];
  30. }
  31. }
  32. }
  33. //去重
  34. for (int j = 1; j < i; j++){
  35. if (Price[i] == Price[j]){
  36. Solution[j] = 0;
  37. }
  38. }
  39. }
  40. int Answer = 0;
  41. for (int i = 1; i <= n; i++){
  42. if (Length[i] == MaxLength){ //找到每一个子序列长度都为最大长度的子序列
  43. Answer += Solution[i];
  44. }
  45. }
  46. cout << MaxLength << " " << Answer;
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注