NC20280. [SCOI2010]股票交易
描述
输入描述
输入数据第一行包括3个整数，分别是T，MaxP，W。接下来T行，第i行代表第i-1天的股票走势，每行4个整数，分别表示APi，BPi，ASi，BSi。
输出描述
输出数据为一行，包括1个数字，表示lxhgww能赚到的最多的钱数。
示例1
输入:
5 2 0 2 1 1 1 2 1 1 1 3 2 1 1 4 3 1 1 5 4 1 1
输出:
3
C++11(clang++ 3.9) 解法, 执行用时: 49ms, 内存消耗: 16124K, 提交时间: 2020-07-23 20:05:36
#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005],q[2005],t,maxp,w;
int main(){
scanf("%d %d %d",&t,&maxp,&w);
for(int i=0;i<=2000;++i) for(int j=0;j<=2000;++j) dp[i][j]=-10086001;
for(int i=1;i<=t;++i)
{
int ap,bp,as,bs;
scanf("%d %d %d %d",&ap,&bp,&as,&bs);
for(int j=0;j<=as;++j) dp[i][j]=-j*ap;
for(int j=0;j<=maxp;++j) dp[i][j]=max(dp[i][j],dp[i-1][j]);
if(i<=w) continue;
int l,r;
l=1,r=0;
for(int j=0;j<=maxp;++j)
{
while(l<=r && q[l]<j-as) ++l;
while(l<=r && dp[i-w-1][q[r]]+q[r]*ap<=dp[i-w-1][j]+j*ap) --r;
q[++r]=j;
dp[i][j]=max(dp[i][j],dp[i-w-1][q[l]]+q[l]*ap-j*ap);
}
l=1,r=0;
for(int j=maxp;~j;--j)
{
while(l<=r && q[l]>j+bs) ++l;
while(l<=r && dp[i-w-1][q[r]]+q[r]*bp<=dp[i-w-1][j]+j*bp) --r;
q[++r]=j;
dp[i][j]=max(dp[i][j],dp[i-w-1][q[l]]+q[l]*bp-j*bp);
}
}
printf("%d",dp[t][0]);
return 0;
}