HDU 3401 Trade

时间：2015-09-12 10:49:57 阅读：212 评论：0 收藏：0 [点我收藏+]

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.

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.

Output

The most money lxhgww can earn.

Sample Input

Sample Output

Source

HDOJ Monthly Contest – 2010.05.01

解题：单调队列优化dp

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2010;
 4 const int INF = 0x3f3f3f3f;
 5 int dp[maxn][maxn],q[maxn],p[maxn],hd,tl;
 6 
 7 int main(){
 8     int kase,ap,bp,as,bs,n,m,w;
 9     scanf("%d",&kase);
10     while(kase--){
11         scanf("%d%d%d",&n,&m,&w);
12         for(int i = 1; i <= w + 1; ++i){
13             scanf("%d%d%d%d",&ap,&bp,&as,&bs);
14             for(int j = 0; j <= m; ++j){
15                 dp[i][j] = j <= as?-ap*j:-INF;
16                 if(i > 1) dp[i][j] = max(dp[i][j],dp[i-1][j]);
17             }
18         }
19         for(int i = w + 2; i <= n; ++i){
20             scanf("%d%d%d%d",&ap,&bp,&as,&bs);
21             int k = i - w - 1;
22             hd = tl = 0;
23             for(int j = 0; j <= m; ++j){
24                 int tmp = dp[k][j] - ap*(m - j);
25                 while(hd < tl && p[tl-1] < tmp) --tl;
26                 q[tl] = j;
27                 p[tl++] = tmp;
28                 while(hd < tl && j - q[hd] > as) ++hd;
29                 dp[i][j] = max(dp[i-1][j],p[hd] + ap*(m - j));
30             }
31             hd = tl = 0;
32             for(int j = m; j >= 0; --j){
33                 int tmp = dp[k][j] + bp*j;
34                 while(hd < tl && p[tl-1] < tmp) --tl;
35                 q[tl] = j;
36                 p[tl++] = tmp;
37                 while(q[hd] - j > bs) ++hd;
38                 dp[i][j] = max(dp[i][j],p[hd] - bp*j);
39             }
40         }
41         printf("%d\n",dp[n][0]);
42     }
43     return 0;
44 }

View Code

HDU 3401 Trade

原文：http://www.cnblogs.com/crackpotisback/p/4802621.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)