题面
Sol
设(f[i][j])表示第(i)天有(j)张股票的最大收益
转移很简单辣
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(2010);
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int t, maxp, w, ap[_], bp[_], as[_], bs[_];
int f[_][_], ans = -2e9;
int main(RG int argc, RG char* argv[]){
t = Input(), maxp = Input(), w = Input();
for(RG int i = 1; i <= t; ++i)
ap[i] = Input(), bp[i] = Input(), as[i] = Input(), bs[i] = Input();
Fill(f, -127), f[0][0] = 0;
for(RG int i = 1; i <= t; ++i){
for(RG int j = 0; j <= maxp; ++j) f[i][j] = f[i - 1][j];
for(RG int j = 0; j <= as[i] && j <= maxp; ++j) f[i][j] = max(f[i][j], -j * ap[i]);
if(i <= w) continue;
for(RG int j = 0; j <= maxp; ++j){
for(RG int k = j - 1; ~k && j - k <= as[i]; --k)
f[i][j] = max(f[i][j], f[i - w - 1][k] - (j - k) * ap[i]);
for(RG int k = j + 1; k <= maxp && k - j <= bs[i]; ++k)
f[i][j] = max(f[i][j], f[i - w - 1][k] + (k - j) * bp[i]);
}
}
for(RG int i = 0; i <= maxp; ++i) ans = max(ans, f[t][i]);
printf("%d
", ans);
return 0;
}
转移方程提出来与(k)无关的然后单调队列辣
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(2010);
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int t, maxp, w, ap[_], bp[_], as[_], bs[_];
int Q[_], head, tail, g[_];
int f[_][_], ans = -2e9;
int main(RG int argc, RG char* argv[]){
t = Input(), maxp = Input(), w = Input();
for(RG int i = 1; i <= t; ++i)
ap[i] = Input(), bp[i] = Input(), as[i] = Input(), bs[i] = Input();
Fill(f, -127), f[0][0] = 0;
for(RG int i = 1; i <= t; ++i){
for(RG int j = 0; j <= maxp; ++j) f[i][j] = f[i - 1][j];
for(RG int j = 0; j <= as[i] && j <= maxp; ++j) f[i][j] = max(f[i][j], -j * ap[i]);
if(i <= w) continue;
head = 0, tail = -1;
for(RG int j = 0; j <= maxp; ++j){
while(head <= tail && j - Q[head] > as[i]) ++head;
if(head <= tail && j > Q[head]) f[i][j] = max(f[i][j], g[head] - j * ap[i]);
while(head <= tail && g[tail] < f[i - w - 1][j] + j * ap[i]) --tail;
Q[++tail] = j, g[tail] = f[i - w - 1][j] + j * ap[i];
}
head = 0, tail = -1;
for(RG int j = maxp; ~j; --j){
while(head <= tail && Q[head] - j > bs[i]) ++head;
if(head <= tail && Q[head] > j) f[i][j] = max(f[i][j], g[head] - j * bp[i]);
while(head <= tail && g[tail] < f[i - w - 1][j] + j * bp[i]) --tail;
Q[++tail] = j, g[tail] = f[i - w - 1][j] + j * bp[i];
}
}
for(RG int i = 0; i <= maxp; ++i) ans = max(ans, f[t][i]);
printf("%d
", ans);
return 0;
}