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