洛谷1108 低價購買 -开发者知识库

洛谷1108 低價購買 -开发者知识库,第1张

題目描述

“低價購買”這條建議是在奶牛股票市場取得成功的一半規則。要想被認為是偉大的投資者,你必須遵循以下的問題建議:“低價購買;再低價購買”。每次你購買一支股票,你必須用低於你上次購買它的價格購買它。買的次數越多越好!你的目標是在遵循以上建議的前提下,求你最多能購買股票的次數。你將被給出一段時間內一支股票每天的出售價(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

輸出樣例#1:

BUYLOW.OUT
4 2

解題思路
第一問就是最基本的最長下降子序列,問題的關鍵在第二問,這里我們可以采用一種貪心的思路,當發現兩個值相等就把后面的那個值賦值為0,畢竟同樣的大小,選前面的總是比選后面的要好啊
 1 var n,i,j,max,ans:longint;    
2 m,f,t:array[0..5000]of longint;
3 begin
4 readln(n);
5 fillchar(f,sizeof(f),0);
6 fillchar(t,sizeof(t),0);
7 max:=0;
8 for i:=1 to n do
9 begin
10 read(m[i]);
11 for j:=1 to i-1 do
12 if (m[j]>m[i])and(f[j]>f[i]) then
13 f[i]:=f[j];
14 inc(f[i]);
15 if f[i]=1 then t[i]:=1;
16 for j:=1 to i-1 do
17 if (f[i]-1=f[j])and(m[j]>m[i]) then inc(t[i],t[j])
18 else if (m[j]=m[i])and(f[i]=f[j]) then t[j]:=0; //類似這個樣子
19 if f[i]>max then max:=f[i];
20 end;
21 ans:=0;
22 for i:=1 to n do
23 if f[i]=max then inc(ans,t[i]);
24 writeln(max,' ',ans);
25 end.

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复