把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
HDU 3401 Trade
题目大意：有个T天，最多手上拿P张股票，每次进行购买股票或出售的操作之后都要隔W天才能再下一次操作，T天中第i天时，每张股票购入加格为ap[i]，出售价格为bp[i]，最多购买as[i]张，最多出售bp[i]张，一天不能同时买和卖，假设开局金钱无限，求最多能赚多少钱，所有数据范围为2000以内。
解：
很容易看出的是可以通过持有股票的张数来进行状态转移，间隔W天或以上的问题可以通过最大前缀转化为间隔刚好W天，那么设定状态dp[i][j]为第i天手上还有j张股票的时候最大的赚钱量（为什么有无后效性就不再阐述了，倒着推就行）。此时状态转移为
dp[i][j]=max(dp[i-1][j],dp[i-W-1][k]+delta)这时买和卖可以分开考虑，之后的dp[i-W-1][k]+delta可以分解为dp[i-W-1][j-k] - kap[i]和dp[i-W-1][j+k] +kbp[i]，但是如果去枚举k的话复杂度为O(n3)，寄。
分解我们刚刚得到的公式dp[i-W-1][j-k]-k*ap[i]，其中ap[i]是固定的，但j-k和k是变化的，这导致了没有单调性的问题，但我们可以转化公式为dp[i-W-1][j-k]+(j-k-j)*ap[i]，这样就把j-k和k独立出来，也就是对于每个j，求比它小的数j-k，使得dp[i-W-1][j-k]+(j-k)*ap[i]最大，而且k有范围的要求，于是我们使用单调队列进行优化，并对卖的情况同样进行操作，复杂度优化到了O(4n2)。
这是典型的通过分离项来将两个独立的参量的影响变为单个参量的影响，如果没有每天的购买出售限制的话，不用单调队列而用sort也是可以的，不过因为这里的递推是顺序的，后面的值一定是由前面的值得出，所以你永远可以相信单调队列。
代码
代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#define ll long long
#define maxn 1000005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define cst 130000
using namespace std;
int dp[2001][2001];
int qr[2001],rk[2001];
int ap[2001], bp[2001], as[2001], bs[2001];
int main() {
cfast;
int t;
cin >> t;
while (t--) {
int n, p, w;
cin >> n >> p >> w;
inc(i,1, n+1) {
cin >> ap[i] >> bp[i] >> as[i] >> bs[i];
}
int ans = 0;
inc(i, 1, n+1) {
inc(j, 0, p+1) {
if (j <= as[i]) {
dp[i][j] = -j * ap[i];
}
else dp[i][j] = -1e9;
}
}
inc(i, 2, n + 1) {
inc(j, 0, p + 1) {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
if (i - w - 1 >= 1) {
int from = i - w - 1;
int head = 0, tail = -1;
inc(j, 0, p + 1) {
ll now = dp[from][j] + j * ap[i];
while (head <= tail && qr[tail] <= now) {
tail--;
}
tail++;
qr[tail] = now;
rk[tail] = j;
while (head <= tail && j - as[i] > rk[head])head++;
dp[i][j] = max(dp[i][j], qr[head] - j * ap[i]);
}
head = 0, tail = -1;
for (int j = p; j >= 0; j--) {
ll now = dp[from][j] + j * bp[i];
while (head <= tail && qr[tail] <= now) {
tail--;
}
tail++;
qr[tail] = now;
rk[tail] = j;
while (head <= tail && j + bs[i] < rk[head])head++;
dp[i][j] = max(dp[i][j], qr[head] - j * bp[i]);
if (i == n) {
ans = max(ans, dp[i][j]);
}
}
}
}
cout << ans << endl;
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
