3224 - 布丁
FJ建立了一个布丁工厂。在接下来的N(1<=N<=40,000)个星期里，原料牛奶和劳动力的价格会有很大波动。FJ希望能够在满足消费者需求的前提下尽量减小花费。
FJ预计接下来每个星期会需要Ci(1<=Ci<=5,000)元钱来生产一单位布丁，且消费者会需要Pi(0<=Pi<=10,000)单位布丁。
FJ每星期即可以生产布丁，也可以储存布丁供以后使用。它的仓库存储一星期一单位布丁需要S(1<=S<=100)元钱。但是由于布丁有保质期，所以最多只能保存T(0<=T<=40,000)星期。也就是说x星期生产的布丁可以在(x+T)星期销售，但是不能在(x+T+1)星期销售。
请帮助FJ安排生产与存储的方案使得在满足消费者需求的前提下尽量减小花费。
Input
第一行为N,S与T.
第二行到第(N+1)行：每一行两个数，即Ci与Pi。
Output
仅一个数，即满足顾客需求前提下的最小花费。
Examples
Input
5 10 3 12 1 21 2 27 4 45 5 52 3
Output
488
Hint
【数据范围及约定】
对于50%的数据，满足1<=N<=5000,1<=T<=5000；
对于100%的数据，见题目描述。
Solution C++
#include <cstdio> #include <cstring> #include <cmath> #include <climits> #include <cstdlib> #include <algorithm> #define MAXN 50010 #define LL long long using namespace std; int N=0,S=0,T=0; int C[MAXN]={0},P[MAXN]={0}; int Q[MAXN*10]={0}; int head=1,tail=0; inline int Get(int p){ while(head<=tail && p-Q[head]>T) head++; return Q[head]; } inline void Push(int x){ while(head<=tail && S*(x-Q[tail])+C[Q[tail]] >C[x] ) tail--; Q[++tail]=x; } int main(){ //freopen("pudding.in","r",stdin); //freopen("pudding.out","w",stdout); scanf("%d%d%d",&N,&S,&T); for(int i=1;i<=N;++i) scanf("%d%d",&C[i],&P[i]); /*暴力！！！ for(int i=1;i<=N;++i){ for(int j=1;j<=T && i+j<=N;++j){ if(C[i]+S*j < C[i+j]){ C[i+j]=C[i]+S*j; } } } LL Ans=0; for(int i=1;i<=N;++i) Ans+=P[i]*C[i];*/ LL Ans=0; int pos; for(int i=1;i<=N;++i){ Push(i); pos=Get(i); Ans+=P[i]*(S*(i-pos)+C[pos]); } printf("%lld",Ans); fclose(stdin); fclose(stdout); return 0; }
Hint
【数据范围及约定】
对于50%的数据，满足1<=N<=5000,1<=T<=5000；
对于100%的数据，见题目描述。