| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:MS我是贪心过的..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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator