信息學奧賽一本通1302 1302：股票買賣 時間限制: 1000 ms 記憶體限制: 65536 KB 【題目描述】 最近越來越多的人都投身股市，阿福也有點心動了。謹記著“股市有風險，入市需謹慎”，阿福決定先來研究一下簡化版的股票買賣問題。 假設阿福已經準確預測出了某隻股票在未來N天的價格，他希望買 ...
信息學奧賽一本通1302
1302：股票買賣 時間限制: 1000 ms 記憶體限制: 65536 KB
【題目描述】
最近越來越多的人都投身股市，阿福也有點心動了。謹記著“股市有風險，入市需謹慎”，阿福決定先來研究一下簡化版的股票買賣問題。 假設阿福已經準確預測出了某隻股票在未來N天的價格，他希望買賣兩次，使得獲得的利潤最高。為了計算簡單起見，利潤的計算方式為賣出的價格減去買入的價格。 同一天可以進行多次買賣。但是在第一次買入之後，必須要先賣出，然後才可以第二次買入。 現在，阿福想知道他最多可以獲得多少利潤。
【輸入】
輸入的第一行是一個整數T(T≤50)，表示一共有T組數據。 接下來的每組數據，第一行是一個整數N(1≤N≤100,000)，表示一共有N天。第二行是 N 個被空格分開的整數，表示每天該股票的價格。該股票每天的價格的絕對值均不會超過1,000,000。
【輸出】
對於每組數據，輸出一行。該行包含一個整數，表示阿福能夠獲得的最大的利潤。
【輸入樣例】 .
3 7 5 14 -2 4 9 3 17 6 6 8 7 4 1 -2 4 18 9 5 2
【輸出樣例】
28 2 0 解決思路 對於這道題，明顯每一天的最大利潤與之前的日子的利潤有關，而與後面的利潤無關。所以此該題符合無後效性原則，且每天的利潤可由前一天的狀態更新出來，那麼該題可用動態規劃的思路解決。
【數組定義】：
設置函數f[i][j][k]數組用於存儲dp的結果，即到第i天，進行第j次交易，狀態為k時的總利潤。i代表第幾天，j代表第幾次交易，對於k，k=0時代表這一天不持有股票，k=1時代表這一天持有股票。 data[]存放每天的股票的價值
【狀態轉移】
對於f[i][j][0],意味著此時不持有股票，那麼今天不擁有股票，可能是因為前一天不擁有，那麼到目前為止的總利潤不變。也可能是前一天擁有股票，但是今天賣出了，此時也收穫了大小為data[i]的利益而。f[i][j][1]應取這兩種情況的最大值。用代碼表示就是：
f[i][j][0]=max(f[i][j][0],f[i][j][1]+data[i]);
對於f[i][j][1]，意味著目前具有股票，當前具有股票，可能是因為上一天的股票保留到了今天，利潤不變。也可能是因為前一天本來沒有股票，今天購入了股票，利潤減少data[i]。而f[i][j][1]應取這兩種情況的最大值。用代碼表示就是：
f[i][j][1]=max(f[i][j-1][0]-data[i],f[i][j][1]);
【代碼示例】
1 #include <bits/stdc++.h>
using namespace std; 2 3 int data[100005],f[3][3]; 4 5 int max(int a,int b) { 6 return a>b?a:b; 7 } 8 9 int min(int a,int b) { 10 return a<b?a:b; 11 } 12 13 int main() { 14 int t,n; 15 cin>>t; 16 while(t--) { 17 18 memset(f,0,sizeof(f)); 19 cin>>n; //三個維度的意義為：第幾天，第幾次交易，手中是否持有股票 20 f[0][0]=0; 21 f[0][1]=-1e8; 22 f[1][1]=-1e8; 23 f[1][0]=0; 24 f[2][1]=-1e8; 25 for(int i=1; i<=n; i++) { 26 scanf("%d",&data[i]); 27 } 28 for(int i=1; i<=n; i++) { 29 for(int j=1; j<=2; j++) { 30 f[i][j][0]=max(f[i][j][0],f[i][j][1]+data[i]); 31 f[i][j][1]=max(f[i][j-1][0]-data[i],f[i][j][1]); 32 } 33 } 34 printf("%d\n",f[n][2][0]); 35 }
【空間優化】 我們發現f[i]都是由f[i-1]更新得到的，所以我們可以不用設置[i]這一維度，我們只需要從上一次記錄的結果再進行更新就好了，代碼如下
1 #include <iostream> 2 using namespace std; 3 4 int data[100005],f1[100005],f2[100005]; 5 int mmin=1e7,mmax=-1e7; 6 7 int max(int a,int b){ 8 return a>b?a:b; 9 } 10 11 int min(int a,int b){ 12 return a<b?a:b; 13 } 14 15 int main(){ 16 int t ; 17 cin>> t ; 18 while(t--){ 19 int n,ans=0; 20 cin>>n; 21 for(int i=1;i<=n;i++){ 22 scanf("%d",&data[i]); 23 } 24 mmin=1e7,mmax=-1e7; 25 for(int i=2;i<=n;i++) 26 { 27 mmin=min(mmin,data[i]); 28 f1[i]=max(f1[i-1],data[i]-mmin); 29 } 30 f2[n+1]=0; 31 mmin=1e7,mmax=-1e7; 32 for(int i=n-1;i>=1;i--) 33 { 34 mmax=max(mmax,data[i]); 35 f2[i]=max(f2[i+1],mmax-data[i]); 36 37 } 38 for(int i=1;i<n;i++){ 39 ans=max(ans,f1[i]+f2[i+1]); 40 } 41 printf("%d\n",ans); 42 } 43 return 0; 44 }
PS：個人日常發佈學習筆記，本篇思路從【董曉老師】處學習
董曉老師博客：https://www.cnblogs.com/dx123/
