题解【洛谷P2569】[SCOI2010]股票交易
题面
设 \(dp_{i,j}\) 表示前 \(i\) 天,现在手里有 \(j\) 股的最大收益。
转移需要分情况讨论:
- 这一天不进行任何交易,即 \(dp_{i,j} = dp_{i - 1, j}\);
- 这一天买股票:
- 在之前没有买过股票的情况下买股票:\(dp_{i,j}=-j\times AP_{i}\)(\(0\le j\le AS_i\));
- 在之前的基础上买:\(dp_{i,j}=dp_{i-w-1,k}-(j-k)\times AP_i\)(\(j-AS_i\le k\le j\))\((\alpha)\)。
- 这一天卖股票:
- 在之前的基础上卖:\(dp_{i,j}=dp_{i-w-1,k}+(k-j)\times BP_i\)(\(j\le k\le j+BS_i\))\((\beta)\)。
前两种情况可以直接维护,而后两种情况暴力是 \(\mathcal O (T^2MaxP)\) 的,考虑如何优化。
先化简一下式子:
- \((\alpha)dp_{i,j}=dp_{i-w-1,k}+k\times AP_i-j\times AP_i(j-AS_i\le k\le j)\),
- \((\beta)dp_{i,j}=dp_{i-w-1,k}+k\times BP_i-j\times AP_i(j\le k\le j+BS_i)\)。
我们发现这两个式子中 \(k\) 的取值都是在一段区间中,于是滑动窗口维护区间最值,可以使用单调队列。
这样我们就可以 AC 此题了。
#include
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PIII;
template
inline T gi()
{
T f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int INF = 0x3f3f3f3f, N = 2003, M = N << 1;
int n, maxp, w;
int ap[N], bp[N], as[N], bs[N];
int dp[N][N];
int q[N], hh, tt;
int main()
{
//File("");
n = gi (), maxp = gi (), w = gi ();
for (int i = 1; i <= n; i+=1)
ap[i] = gi (), bp[i] = gi (), as[i] = gi (), bs[i] = gi ();
memset(dp, 0xcf, sizeof dp);
for (int i = 1; i <= n; i+=1)
{
for (int j = 0; j <= as[i]; j+=1)
dp[i][j] = -j * ap[i];
for (int j = 0; j <= maxp; j+=1)
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
if (i <= w) continue;
q[hh = tt = 1] = 0;
for (int j = 0; j <= maxp; j+=1)
{
while (hh <= tt && q[hh] < j - as[i]) ++hh;
while (hh <= tt && dp[i - w - 1][q[tt]] + q[tt] * ap[i] < dp[i - w - 1][j] + j * ap[i]) --tt;
q[++tt] = j;
if (hh <= tt) dp[i][j] = max(dp[i][j], dp[i - w - 1][q[hh]] + q[hh] * ap[i] - j * ap[i]);
}
q[hh = tt = 1] = maxp + 1;
for (int j = maxp; j >= 0; j-=1)
{
while (hh <= tt && q[hh] > j + bs[i]) ++hh;
while (hh <= tt && dp[i - w - 1][q[tt]] + q[tt] * bp[i] < dp[i - w - 1][j] + j * bp[i]) --tt;
q[++tt] = j;
if (hh <= tt) dp[i][j] = max(dp[i][j], dp[i - w - 1][q[hh]] + q[hh] * bp[i] - j * bp[i]);
}
}
printf("%d\n", *max_element(dp[n], dp[n] + 1 + maxp));
return 0;
}