$f[i][j]$ 表示第i天,手中股票数为j的最优解
初始化 $f[i][0]=0$ $0<=i<=n$
4种方式转移
可以将 $f[i-w-1][k]+k*as$ 和 $f[i-w-1][k]+k*bs$ 放到单调队列中
#include
#include
#include
#define N 3001
using namespace std;
int n, m, w, ap, bp, as, bs, t, h, ans;
int f[N][N], q[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
int main()
{
int i, j;
n = read();
m = read();
w = read();
memset(f, -127, sizeof(f));
for(i = 0; i <= n; i++) f[i][0] = 0;
for(i = 1; i <= n; i++)
{
ap = read();
bp = read();
as = read();
bs = read();
for(j = 1; j <= as; j++) f[i][j] = -ap * j;
for(j = 0; j <= m; j++) f[i][j] = max(f[i][j], f[i - 1][j]);
if(i - w - 1 >= 0)
{
h = 1, t = 0;
for(j = 0; j <= m; j++)
{
while(h <= t && f[i - w - 1][q[t]] + q[t] * ap < f[i - w - 1][j] + j * ap) t--;
q[++t] = j;
while(h <= t && q[h] < j - as) h++;
f[i][j] = max(f[i][j], f[i - w - 1][q[h]] + q[h] * ap - j * ap);
}
h = 1, t = 0;
for(j = m; j >= 0; j--)
{
while(h <= t && f[i - w - 1][q[t]] + q[t] * bp < f[i - w - 1][j] + j * bp) t--;
q[++t] = j;
while(h <= t && q[h] > j + bs) h++;
f[i][j] = max(f[i][j], f[i - w - 1][q[h]] + q[h] * bp - j * bp);
}
}
}
for(i = 0; i <= m; i++) ans = max(ans, f[n][i]);
printf("%d\n", ans);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章