Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:MS我是贪心过的..

Posted by Liuzhaoliang at 2009-08-17 20:51:06 on Problem 2393
In Reply To:Re:MS我是贪心过的.. Posted by:10074187 at 2008-08-25 16:19:33
应该不能只考虑相邻的,它之前的周都要考虑,不过有个临界值吧,到达这个临界值,前面的周都忽略。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 10000
long long cost[N],req[N];
int n,s;
int main(){
	long long ans=0;
	scanf("%d%d",&n,&s);
	for(int i=0;i<n;i++)
		scanf("%lld%lld",cost+i,req+i);
	ans+=cost[0]*req[0];
	for(int i=1;i<n;i++){
		long long tmp;
		long long t=tmp=cost[i]*req[i];
		for(int j=i-1;j>=0;j--){
			tmp=min(tmp,cost[j]*req[i]+(i-j)*s*req[i]);
			if( (i-j)*s*req[i]>=t) break;
		}
		ans+=tmp;
	}
	printf("%lld\n",ans);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator