对于100%的数据,0<=W<T<=2000,1<=MaxP<=2000
对于所有的数据,1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP
题解:#include<cstdio>
#include<cstdlib>
#include<deque>
#include<algorithm>
using namespace std;
const int N = 2200;
const int MAX = 2.1E9;
int n,m,w,buy[N][2],lim[N][2],f[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
int dui[N],dl,dr,pos[N];
int main(){
int i,j;
//freopen("in.txt","r",stdin);
n=scan();m=scan();w=scan();
for(i=1;i<=n;i++){
scanf("%d%d%d%d",&buy[i][0],&buy[i][1],&lim[i][0],&lim[i][1]);
}
for(i=1;i<=n;i++)
for(j=0;j<=m;j++){
if(j<=lim[i][0])f[i][j] = -j*buy[i][0];
else f[i][j]=-MAX;
}
for(i=2;i<=n;i++){
for(j=0;j<=m;j++)
f[i][j] = max(f[i][j],f[i-1][j]);
int i2=i-w-1;
if(i2<=0)continue;
//buy
dl=1;dr=0;
for(j=0;j<=m;j++){
//pop front
while(dl<=dr && j-pos[dl] > lim[i][0])dl++;
if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][0]);
//push now
int val = f[i2][j]+j*buy[i][0];
while(dl<=dr && dui[dr]<=val)dr--;
dr++;
dui[dr] = val;
pos[dr] = j;
}
//sell
dl=1;dr=0;
for(j=m;j>=0;j--){
//pop front
while(dl<=dr && pos[dl]-j > lim[i][1])dl++;
if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][1]);
//push now
int val = f[i2][j]+j*buy[i][1];
while(dl<=dr && dui[dr]<=val)dr--;
dr++;
dui[dr] = val;
pos[dr] = j;
}
}
printf("%d\n",f[n][0]);
return 0;
}
评论