记录编号	86694	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2014-01-27 17:38:20	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
#include<set>
using namespace std;
const int SIZEN=5010;
int Tpre[SIZEN]={0},f[SIZEN]={0},F[SIZEN]={0};
int N,S;
deque<int> Q;
int D[SIZEN]={0};
int t(int i,int j){return Tpre[j]-Tpre[i-1];}//[i,j]的时间和
void DP(void){
	Q.push_back(N+1);
	D[N+1]=0;
	for(int i=N;i>=1;i--){
		//若g(Q[1],Q[0])<=f[i],则Q[0]对以后的决策不会再有用
		while(Q.size()>1&&f[i]*t(Q[1],Q[0]-1)>=D[Q[1]]-D[Q[0]]) Q.pop_front();
		//此时Q[0]是最优决策,即i应被划分为:i~Q[0]-1和Q[0]~N
		D[i]=D[Q[0]]+f[i]*(S+t(i,Q[0]-1));
		while(Q.size()>1){
			int qn=Q.size();
			//若g(i,Q[qn-1])<=g(Q[qn-1],Q[qn-2]),则删去状态Q[qn-1]
			if((D[i]-D[Q[qn-1]])*t(Q[qn-1],Q[qn-2]-1)<=(D[Q[qn-1]]-D[Q[qn-2]])*t(i,Q[qn-1]-1)) Q.pop_back();
			else break;
		}
		Q.push_back(i);
	}
	cout<<D[1]<<endl;
}
void read(void){
	scanf("%d%d",&N,&S);
	for(int i=1;i<=N;i++) scanf("%d%d",&Tpre[i],&F[i]),Tpre[i]+=Tpre[i-1];
	//事实上,t函数调用的时候是不会计算某个点到N+1的T和的
	for(int i=N;i>=1;i--) f[i]=f[i+1]+F[i];
}
int main(){
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	read();
	DP();
	return 0;
}