比赛 20090916练习赛 评测结果 AAAAAAWWWW
题目名称 任务安排 最终得分 60
用户昵称 Makazeu 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-10-17 21:04:09
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MAXN 200000000
#define Max 6002
using namespace std;
int S;
int N;
class BATCH
{
public:
	int T;
	int F;
}B[Max];

int TT[Max];
int TF[Max];
int F[Max];

void init()
{
	cin>>N>>S;
	for (int i=1;i<=N;i++)
		cin>>B[i].T>>B[i].F;
	for (int i=1;i<=N;i++)
		F[i]=MAXN;
	for (int i=N;i>=1;i--)
	{
		TT[i]=TT[i+1]+B[i].T;
		TF[i]=TF[i+1]+B[i].F;
	}
}

void Dynamic()
{
	for (int i=N;i>=1;i--)
	{
		for (int j=i+1;j<=N+1;j++)
		{
			if (F[i]>(F[j]+(S+TT[i]-TT[j])*TF[i] ))
				F[i]=F[j]+(S+TT[i]-TT[j])*TF[i];
		}
	}
}



int main()
{
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	init();
	Dynamic();
	cout<<F[1]<<endl;
	return 0;
}