@fuheimao
2015-09-25T21:01:28.000000Z
字数 1742
阅读 721
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
第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结尾的子序列。
【代码】(貌似需要高精度但是没写)
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int Price[5001] = {0}, Solution[5001] = {0}, Length[5001] = {0};
int n;
int MaxLength = -1;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> Price[i];
}
Length[1] = 1;
Solution[1] = 1;
for (int i = 2; i <= n; i++){
//求最长下降子序列
for (int j = i - 1; j >= 1; j--){
if (Price[i] < Price[j] && Length[i] < Length[j]){
Length[i] = Length[j];
}
}
Length[i]++;
MaxLength = Max(MaxLength, Length[i]);
//求方案数
if (Length[i] == 1){
Solution[i] = 1;
}else{
for (int j = 1; j < i; j++){
if (Price[j] > Price[i] && Length[i] == Length[j] + 1){
Solution[i] += Solution[j];
}
}
}
//去重
for (int j = 1; j < i; j++){
if (Price[i] == Price[j]){
Solution[j] = 0;
}
}
}
int Answer = 0;
for (int i = 1; i <= n; i++){
if (Length[i] == MaxLength){ //找到每一个子序列长度都为最大长度的子序列
Answer += Solution[i];
}
}
cout << MaxLength << " " << Answer;
return 0;
}