bzoj1855: [Scoi2010]股票交易

1855: [Scoi2010]股票交易

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1132 Solved: 550
[Submit][Status][Discuss]

Description

最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖出BSi股。另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过MaxP。在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

Input

输入数据第一行包括3个整数，分别是T，MaxP，W。接下来T行，第i行代表第i-1天的股票走势，每行4个整数，分别表示APi，BPi，ASi，BSi。

Output

输出数据为一行，包括1个数字，表示lxhgww能赚到的最多的钱数。

Sample Input

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

Sample Output

HINT

对于30%的数据，0 < =W<t <="50,1"> 对于50%的数据，0 < =W<t <="2000,1"> 对于100%的数据，0 < =W<t <="2000,1">
对于所有的数据，1 < =BPi < =APi < =1000,1 < =ASi,BSi < =MaxP

Source

Day1

一道单调队列优化dp

首先想朴素的dp方程

f[i][j]表示第i天手上有j股的利润

对于每一天有三种情况

1、不买不卖

f[i][j]=max(f[i][j],f[i-1][j]);

2、买进

f[i][j]=max(f[i][j],f[k][q]-(j-q)*ap)

3、卖出

f[i][j]=max(f[i][j],f[k][q]+(q-j)*bp)

而对于f[i][j]>=f[i-1][j]（不买不卖）

所以k其实不用枚举，直接取i-w-1即可

而由max操作想到用单掉队列优化

此时将方程转化为（以买进为例）

f[i][j]=max(f[i][j],f[i-w-1][k]+k*ap-j*ap)

此时将f[i-w-1][k]+k*ap丢进单调队列里

接下来顺便讲一下我对单调队列的理解吧

这种东西还是要自己慢慢理解

推荐一篇博客

其实就是在一个区间里取最小值的操作

然后将这个区间一点一点往后挪

将原来的n^2枚举换成线性的复杂度

上代码:

#include<cstdio>
#include<iostream>
#include<cstring>
struct node
{
	int first,second;
}q[2010];
int f[2006][2005];
int main()
{
	memset(f,-127,sizeof(f));
	int T,maxp,w,ans=0;	scanf("%d %d %d",&T,&maxp,&w);
	for(int i=1;i<=T;i++)
	{
		int ap,bp,as,bs;	scanf("%d %d %d %d",&ap,&bp,&as,&bs);
		for(int j=0;j<=as;j++)	f[i][j]=-ap*j;
		for(int j=0;j<=maxp;j++)	f[i][j]=std::max(f[i][j],f[i-1][j]);
		int k=i-w-1;
		if(k>=0)
		{
			int h=0,t=0;
			for(int j=0;j<=maxp;j++)
			{
				while(h<t&&q[h].first+as<j)	h++;
				while(h<t&&q[t-1].second<=f[k][j]+ap*j)	t--;
				q[t].first=j;q[t++].second=f[k][j]+ap*j;
				if(h<t)		f[i][j]=std::max(f[i][j],q[h].second-ap*j);
			}
			h=0,t=0;
			for(int j=maxp;j>=0;j--)
			{	
				while(h<t&&q[h].first-bs>j)	h++;
				while(h<t&&q[t-1].second<=f[k][j]+bp*j)	t--;
				q[t].first=j;q[t++].second=f[k][j]+bp*j;
				if(h<t)		f[i][j]=std::max(f[i][j],q[h].second-bp*j);
			}
		}
		ans=std::max(ans,f[i][0]);
	}
	printf("%d
",ans);
	return 0;
}