一支 股票 algorithm namespace 整数 变形 价格 div
"低价购买" 这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:"低价购买;再低价购买"。每次你购买一支股票, 你必须用低于你上次购买它的价格购买它。买的次数越多越好! 你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价 (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:
- BUYLOW.IN
- 12
- 68 69 54 64 68 64 70 67 78 62 98 87
- BUYLOW.OUT
- 4 2最长不下降子序列变形
- 1#include 2#include 3#include 4#include 5 using namespace std;
- 6 int f[5001],
- g[5001];
- 7 int a[5001];
- 8 int main() 9 {
- 10 int n,
- ans = 0;
- 11 scanf("%d", &n);
- 12
- for (int i = 1; i <= n; i++) scanf("%d", a + i);
- 13
- for (int i = 1; i <= n; i++) 14 {
- 15 f[i] = 1;
- 16
- for (int j = 1; j) 17 {
- 18
- if (a[j] > a[i]) f[i] = max(f[i], f[j] + 1);
- 19
- }
- 20 ans = max(ans, f[i]);
- 21
- }
- 22
- for (int i = 1; i <= n; i++) 23 {
- 24
- if (f[i] == 1) g[i] = 1;
- 25
- for (int j = 1; j) 26 {
- 27
- if (a[i] 1) g[i] += g[j];
- 28
- if (a[i] == a[j] && f[i] == f[j]) f[j] = 0;
- 29
- }
- 30
- }
- 31 int tot = 0;
- 32
- for (int i = 1; i <= n; i++) 33
- if (f[i] == ans) 34 tot += g[i];
- 35 printf("%d %d", ans, tot);
- 36
- return 0;
- 37
- }
入门动态规划 洛谷 P1108 低价购买
来源: http://www.bubuko.com/infodetail-2088438.html