洛谷題目連接:[SCOI2010]股票交易

題目描述

最近lxhgww又迷上了投資股票，通過一段時(shí)間的觀察和學(xué)習(xí)，他總結(jié)出了股票行情的一些規(guī)律。

通過一段時(shí)間的觀察，lxhgww預(yù)測(cè)到了未來T天內(nèi)某只股票的走勢(shì)，第i天的股票買入價(jià)為每股APi，第i天的股票賣出價(jià)為每股BPi（數(shù)據(jù)保證對(duì)于每個(gè)i，都有APi>=BPi），但是每天不能無限制地交易，于是股票交易所規(guī)定第i天的一次買入至多只能購(gòu)買ASi股，一次賣出至多只能賣出BSi股。

另外，股票交易所還制定了兩個(gè)規(guī)定。為了避免大家瘋狂交易，股票交易所規(guī)定在兩次交易（某一天的買入或者賣出均算是一次交易）之間，至少要間隔W天，也就是說如果在第i天發(fā)生了交易，那么從第i+1天到第i+W天，均不能發(fā)生交易。同時(shí)，為了避免壟斷，股票交易所還規(guī)定在任何時(shí)間，一個(gè)人的手里的股票數(shù)不能超過MaxP。

在第1天之前，lxhgww手里有一大筆錢（可以認(rèn)為錢的數(shù)目無限），但是沒有任何股票，當(dāng)然，T天以后，lxhgww想要賺到最多的錢，聰明的程序員們，你們能幫助他嗎？

輸入輸出格式

輸入格式：

輸入數(shù)據(jù)第一行包括3個(gè)整數(shù)，分別是T，MaxP，W。

接下來T行，第i行代表第i-1天的股票走勢(shì)，每行4個(gè)整數(shù)，分別表示APi，BPi，ASi，BSi。

輸出格式：

輸出數(shù)據(jù)為一行，包括1個(gè)數(shù)字，表示lxhgww能賺到的最多的錢數(shù)。

輸入輸出樣例

輸入樣例#1：

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

輸出樣例#1：

3

說明

對(duì)于30%的數(shù)據(jù)，0<=W<T<=50,1<=MaxP<=50

對(duì)于50%的數(shù)據(jù)，0<=W<T<=2000,1<=MaxP<=50

對(duì)于100%的數(shù)據(jù)，0<=W<T<=2000,1<=MaxP<=2000

對(duì)于所有的數(shù)據(jù)，1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP

一句話題意: 每天最多可以買進(jìn)\(as_i\)張股票,賣出\(bs_i\)張股票,但是每個(gè)時(shí)刻手中的票最多都只能有\(maxp\)張,每買入一張股票可以獲得\(ap_i\)元,賣出一張股票可以獲得\(bp_i\)元,且如果第\(i\)天進(jìn)行了交易,那么從第\(i+1\)到第\(i+w\)天都不能再進(jìn)行交易,問到第\(n\)天最多可以獲得的價(jià)值.

題解: 這個(gè)數(shù)據(jù)范圍顯然是能DP的.我們先想一下狀態(tài)該如何定義.

首先根據(jù)這個(gè)狀態(tài)轉(zhuǎn)移的條件,有交易的天數(shù)限制,所以顯然是需要一維來存交易到第幾天的.然后是對(duì)于手中持有的股票數(shù)量的限制,顯然至少是需要一重循環(huán)來枚舉目前手中持有的股票數(shù)量的,所以考慮將這個(gè)也加入狀態(tài)中.可得狀態(tài)\(f[i][j]\)表示到第\(i\)天手中持有\(j\)張股票的最大利益.那么最后的答案就是
\(f[n][0]\),因?yàn)轱@然在最后一天把所有股票都賣出不會(huì)比留著股票差.

然后想一下如何轉(zhuǎn)移這個(gè)狀態(tài).那么從上一個(gè)狀態(tài)到現(xiàn)在的狀態(tài)\(f[i][j]\),顯然只有這幾種情況:

• 第\(i-1\)天沒有買/賣股票,第\(i\)天的最大收益為\(f[i-1][j]\).
• 第\(i-w-1\)天進(jìn)行了股票的買賣且擁有\(k(k<j)\)張股票,第\(i\)天有股票\(j\)張,此時(shí)買入了\(j-k\)張股票,可得最大收益為\(f[i][j] = max(f[i][j], f[i-w-1][k]-(j-k)*ap[i])\)
• 第\(i-w-1\)天進(jìn)行了股票的買賣且擁有\(k(k>j)\)張股票,第\(i\)天有股票\(j\)張,此時(shí)賣出了\(k-j\)張股票,可得最大收益為\(f[i][j]=max(f[i][j], f[i-w-1][k]+(k-j)*bp[i])\)

此外沒有別的轉(zhuǎn)移方式了,所以可以列出狀態(tài)轉(zhuǎn)移方程.

那么考慮了狀態(tài)轉(zhuǎn)移之后,仔細(xì)想想發(fā)現(xiàn)這個(gè)時(shí)間復(fù)雜度是\(O(T*maxp^2)\)的,顯然這樣是不能過100%的數(shù)據(jù)的.所以需要使用一些優(yōu)化.

這里我們將這個(gè)狀態(tài)轉(zhuǎn)移方程展開一下,發(fā)現(xiàn):
\[f[i-w-1][k]+(k-j)×bp[i]=(f[i-w-1][k]+k×bp[i])-j×bp[i]\]
也就是說,在枚舉了\(i,j\)的情況下,\(i,j\)是可以看做常數(shù)的,那么此時(shí)對(duì)答案有影響的就只有\(k\)了 .并且我們發(fā)現(xiàn), 如果\(j\)是以正確的順序枚舉的,那么\(k\)也就是逐漸在平移的了.比如說買入股票,那么擁有的股票也就會(huì)越來越多,賣出的話擁有的股票就會(huì)越來越少,事實(shí)上這個(gè)是符合 單調(diào)隊(duì)列優(yōu)化的條件的,所以我們可以考慮將目前擁有的股票數(shù)存入單調(diào)隊(duì)列中,優(yōu)化后復(fù)雜度為\(O(T*maxp)\).

當(dāng)然分開和賣出的兩種情況是要分開使用隊(duì)列的,因?yàn)樗麄兏髯跃哂袉握{(diào)性,但是合起來并沒有.

#include<bits/stdc++.h> using namespace std; const int N=2000+5;int n, maxp, w, ap[N], bp[N], as[N], bs[N], ans = 0; int f[N][N], h1, h2, t1, t2, q1[N], q2[N];int main(){cin >> n >> maxp >> w;for(int i=1;i<=n;i++)cin >> ap[i] >> bp[i] >> as[i] >> bs[i];memset(f, 128, sizeof(f)); f[0][0] = 0;for(int i=1;i<=n;i++){for(int j=0;j<=maxp;j++)f[i][j] = max(f[i][j], f[i-1][j]);for(int j=0;j<=as[i];j++)f[i][j] = max(f[i][j], -1*j*ap[i]);if(i <= w) continue;h1 = h2 = 1, t1 = t2 = 0;for(int j=0;j<=maxp;j++){while(h1 <= t1 && f[i-w-1][q1[t1]]-ap[i]*(j-q1[t1]) <= f[i-w-1][j]) t1--;while(h1 <= t1 && j-q1[h1] > as[i]) h1++;q1[++t1] = j;if(h1 <= t1) f[i][j] = max(f[i][j], f[i-w-1][q1[h1]]-(j-q1[h1])*ap[i]);}h1 = h2 = 1, t1 = t2 = 0;for(int j=maxp;j>=0;j--){while(h2 <= t2 && f[i-w-1][q2[t2]]+bp[i]*(q2[t2]-j) <= f[i-w-1][j]) t2--;while(h2 <= t2 && q2[h2]-j > bs[i]) h2++;q2[++t2] = j;if(h2 <= t2) f[i][j] = max(f[i][j], f[i-w-1][q2[h2]]+(q2[h2]-j)*bp[i]);}}printf("%d\n", f[n][0]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/BCOI/p/9133358.html

總結(jié)

以上是生活随笔為你收集整理的[SCOI2010]股票交易的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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