题解 P2569【 [SCOI2010]股票交易】

P2569 [SCOI2010]股票交易

题目大意:

冷笑话购物网预知了 \(T\) 天的股票走势,已知第 \(i\) 天购入价为每股 \(AP_i\) ,卖出价为每股 \(BP_i\)
(数据保证对于\(\forall i\),都有 \(AP_i \geq BP_i\)
),一次买入至多只能购买 \(AS_i\)股,一次卖出至多只能卖出 \(BS_i\)股。两次交易要间隔 \(W\) 天,且手中的股票不能超过 \(MP\) 股。求赚的最多的钱。

solution:

能感觉到是一道 \(\text{DP}\) 题。我们来设个状态 \(f_{i,j}\) 表示第 \(i\) 天,手中有 \(j\) 股股票的最大收益。

分一下几种情况讨论:

  1. 第 \(i\) 天什么也不干:

\[f_{i,j}=f_{i-1,j} \]

  1. 第 \(i\) 天从 \(0\) 支购进:

\[f_{i,j}=-j\times AP_i,0\leq j \leq j\times AS_i \]

  1. 第 \(i\) 天买进:

\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}-(j-k)\times AP_i\} , j\times AS_i\leq k<j \]

  1. 第 \(i\) 天卖出:

\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}+(k-j)\times BP_i\} , j \leq k < j\times BS_i \]

直接枚举 \(k\) 的话复杂度爆炸,所以我们推一下柿子(以买入为例):

\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}-(j-k)\times AP_i\} \]

打开括号:

\[f_{i,j}=\max \{f_{i,j},f_{i-w-1,k}-j\times AP_i+k\times AP_i\} \]

转化一下,先找出后面柿子的最大值,再和 \(f_{i,j}\) 取 \(\max\) 。

\[f_{i,j}= f_{i-w-1,k}-j\times AP_i+k\times AP_i \]

移项:

\[f_{i,j}= f_{i-w-1,k}+k\times AP_i-j\times AP_i \]

分成两段:

\[f_{i-w-1,k}+k\times AP_i \]

与:

\[j\times AP_i \]

前面那个只跟 \(k\) 有关,后面的是一个定值。就形如:

\[f_i=\max\{f_j+cal(i)\} \]

那么我们把前面的那个柿子扔进单调队列,后面的那个实时算出。就降低了时间复杂度。

细节处理:

  1. 买入时要正序枚举,而卖出时要倒序枚举。因为后面的股票数比前面的大才能卖出。
  2. \(f\) 数组初始化极小值。
  3. 单调队列要初始化头尾。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2003;
int ap,bp,as,bs;
int f[N][N],q[N],hd,tl;
int main(){
	memset(f,0x80,sizeof(f));
	int t,mp,w; scanf("%d%d%d",&t,&mp,&w);
	for(int i=1;i<=t;i++){
		scanf("%d%d%d%d",&ap,&bp,&as,&bs);
		for(int j=0;j<=as;j++)
			f[i][j]=-j*ap;
		for(int j=0;j<=mp;j++)
			f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=w) continue;
		hd=1,tl=0;
		for(int j=0;j<=mp;j++){
			while(hd<=tl&&q[hd]<j-as) hd++;
			while(hd<=tl&&f[i-w-1][q[tl]]+q[tl]*ap<=f[i-w-1][j]+j*ap)
				tl--;
			q[++tl]=j;
			if(hd<=tl) f[i][j]=max(f[i][j],f[i-w-1][q[hd]]+q[hd]*ap-j*ap);
		}
		hd=1,tl=0;
		for(int j=mp;j>=0;j--){
			while(hd<=tl&&q[hd]>bs+j) hd++;
			while(hd<=tl&&f[i-w-1][q[tl]]+q[tl]*bp<=f[i-w-1][j]+j*bp)
				tl--;
			q[++tl]=j;
			if(hd<=tl) f[i][j]=max(f[i][j],f[i-w-1][q[hd]]+q[hd]*bp-j*bp);
		}	
	}
	int ans=0;
	for(int i=0;i<=mp;i++)
		ans=max(ans,f[t][i]);
	printf("%d",ans);	
	return 0;
}

最后附上丑陋手迹题解 P2569【 [SCOI2010]股票交易】

End

上一篇:【WLAN】AP上线、SSID认证


下一篇:1561E - Bottom-Tier Reversals