游客 注册 | 登录
中文 | En

3224 - 布丁

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

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安排生产与存储的方案使得在满足消费者需求的前提下尽量减小花费。

题目输入

第一行为N,S与T.

第二行到第(N+1)行：每一行两个数，即Ci与Pi。

题目输出

仅一个数，即满足顾客需求前提下的最小花费。

输入/输出样例

输入格式

5 10 3
12 1
21 2
27 4
45 5
52 3

输出格式

488

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;
}
请先登陆