HDU 3401 Trade
2024-08-27 16:35:47
Trade
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3401
64-bit integer IO format: %I64d Java class name: Main
Recently, lxhgww is addicted to stock, he finds some regular patterns after a few days' study.
He forecasts the next T days' stock market. On the i'th day, you can buy one stock with the price APi or sell one stock to get BPi.
There are some other limits, one can buy at most ASi stocks on the i'th day and at most sell BSi stocks.
Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i'th day, the next trading day must be on the (i+W+1)th day or later.
What's more, one can own no more than MaxP stocks at any time.
He forecasts the next T days' stock market. On the i'th day, you can buy one stock with the price APi or sell one stock to get BPi.
There are some other limits, one can buy at most ASi stocks on the i'th day and at most sell BSi stocks.
Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i'th day, the next trading day must be on the (i+W+1)th day or later.
What's more, one can own no more than MaxP stocks at any time.
Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn?
Input
The first line is an integer t, the case number.
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi,BPi,ASi,BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi,BPi,ASi,BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.
Output
The most money lxhgww can earn.
Sample Input
1
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
3
Source
解题:单调队列优化dp
考虑买入
$dp[i][j] = max(dp[i-1][j],dp[i - w - 1][k] + (k - j)\times ap$
如何选择k,发现要维护$dp[i-w-1][k] - (m - k)\times ap$
可以根据$dp[i-w-1][k] - (m-k)\times ap + (m - j)\times ap$ 计算出 $dp[i - w - 1][k] + (k - j)\times ap\,k < j$
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f3f;
int dp[maxn][maxn],q[maxn],p[maxn],hd,tl; int main(){
int kase,ap,bp,as,bs,n,m,w;
scanf("%d",&kase);
while(kase--){
scanf("%d%d%d",&n,&m,&w);
for(int i = ; i <= w + ; ++i){
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
for(int j = ; j <= m; ++j){
dp[i][j] = j <= as?-ap*j:-INF;
if(i > ) dp[i][j] = max(dp[i][j],dp[i-][j]);
}
}
for(int i = w + ; i <= n; ++i){
scanf("%d%d%d%d",&ap,&bp,&as,&bs);
int k = i - w - ;
hd = tl = ;
for(int j = ; j <= m; ++j){
int tmp = dp[k][j] - ap*(m - j);
while(hd < tl && p[tl-] < tmp) --tl;
q[tl] = j;
p[tl++] = tmp;
while(hd < tl && j - q[hd] > as) ++hd;
dp[i][j] = max(dp[i-][j],p[hd] + ap*(m - j));
}
hd = tl = ;
for(int j = m; j >= ; --j){
int tmp = dp[k][j] + bp*j;
while(hd < tl && p[tl-] < tmp) --tl;
q[tl] = j;
p[tl++] = tmp;
while(q[hd] - j > bs) ++hd;
dp[i][j] = max(dp[i][j],p[hd] - bp*j);
}
}
printf("%d\n",dp[n][]);
}
return ;
}
最新文章
- C#_Express-ickd接口
- 如何更新firefox中的flash
- Codeforces Round #382 (Div. 2)B. Urbanization 贪心
- IOS沙盒
- stc89c52开发板遥控器解码 红外线发射 内置 eeprom 存储 串口显示编码
- Unity中内置Shader源码的获取方式
- 创建ROS功能包(四)
- 了解Unix进程(2)
- Linux Shell编程(23)——文本处理命令
- SQL 2008 清除数据库日志
- python-面向对象(二)
- CSS3 Media Queries 详细介绍与使用方法
- cc2530-----串口透明传输分析
- Struts2动态方法调用
- django出现__init__() got an unexpected keyword argument &#39;mimetype‘ 问题解决
- ibv_open_device()函数
- ORA-00600[17059]错误
- [bzoj1692] [Usaco2007 Dec]队列变换 (hash||暴力)
- JavaWeb学习(一) ---- HTTP以及Tomcat的安装及使用
- Doctype知识点总结