? ? ? ? ??低價購買（洛谷 1108）

題目描述

“低價購買”這條建議是在奶牛股票市場取得成功的一半規(guī)則。要想被認(rèn)為是偉大的投資者，你必須遵循以下的問題建議:“低價購買；再低價購買”。每次你購買一支股票,你必須用低于你上次購買它的價格購買它。買的次數(shù)越多越好!你的目標(biāo)是在遵循以上建議的前提下，求你最多能購買股票的次數(shù)。你將被給出一段時間內(nèi)一支股票每天的出售價(2^16范圍內(nèi)的正整數(shù))，你可以選擇在哪些天購買這支股票。每次購買都必須遵循“低價購買；再低價購買”的原則。寫一個程序計算最大購買次數(shù)。

這里是某支股票的價格清單：

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

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

最優(yōu)秀的投資者可以購買最多4次股票，可行方案中的一種是：

日期 2 5 6 10

價格 69 68 64 62

輸入輸出格式

輸入格式：

?

第1行: N (1 <= N <= 5000)，股票發(fā)行天數(shù)

第2行: N個數(shù)，是每天的股票價格。

?

輸出格式：

?

輸出文件僅一行包含兩個數(shù):最大購買次數(shù)和擁有最大購買次數(shù)的方案數(shù)(<=2^31)當(dāng)二種方案“看起來一樣”時（就是說它們構(gòu)成的價格隊列一樣的時候）,這2種方案被認(rèn)為是相同的。

?

輸入輸出樣例

輸入樣例#1：

?

BUYLOW.IN 12 68 69 54 64 68 64 70 67 78 62 98 87

輸出樣例#1：

?

?

BUYLOW.OUT 4 2

解題方法

?

就是求最大下降序列，最長長度就是前面（長度最長的并且大于這個數(shù)）的序列的長度+1，個數(shù)就是前面所有（長度等于這個序列的長度-1并且大于這個數(shù)）的序列的個數(shù)相加在一起，記得去重。

代碼

?

<strong>#include<iostream> #include<cstring> using namespace std; int n,maxs,maxg,a[5001],b[5001],f[5001]; bool t[70000]; int main() {cin>>n;for (int i=1;i<=n;i++)cin>>a[i];for (int i=1;i<=n;i++){memset(t,true,sizeof(t)); //用于判斷這個數(shù)用過沒有f[i]=1; //預(yù)處理for (int j=1;j<i;j++)if (a[i]<a[j]) f[i]=max(f[i],f[j]+1); //如果前面的數(shù)大于這個數(shù)，那么當(dāng)前序列=當(dāng)前序列和第j個數(shù)的序列+1較大的for (int j=i-1;j>=1;j--) //越后面的個數(shù)就越多，先用后面的if (t[a[j]] && f[j]==f[i]-1 && a[j]>a[i]) //這個數(shù)用過沒有？長度符合嗎？大于次數(shù)嗎？{b[i]=b[i]+b[j]; t[a[j]]=false; //不能用了 }b[i]=max(b[i],1); //如果沒有就創(chuàng)一個新的maxs=max(maxs,f[i]); //求最大數(shù)}memset(t,true,sizeof(t));for (int i=n;i>=1;i--)if (f[i]==maxs && t[a[i]]) //看看符不符合條件{maxg=maxg+b[i];//個數(shù)相加t[a[i]]=false;}cout<<maxs<<" "<<maxg; }</strong>

?

?

?

?

?

?

?

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的低价购买（洛谷 1108）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。