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 |
贪心900+ms水过.....#include<iostream> #include<stdio.h> #include<algorithm> #include<cstring> #define INT_MAX 1<<30 using namespace std; typedef long long ll; const int INF=0x7F; const int maxn=10000+7; int n,s; struct fuck{ ll c,y; int rep; ll gain; }F[maxn]; ll temp,ans; int main() { scanf("%d%d",&n,&s); for (int i = 0; i < n; i += 1) { scanf("%d%d",&F[i].c,&F[i].y); F[i].rep=i; } for (int i = 0; i < n; i += 1) { for (int j = i+1; j < n; j += 1) { temp=(F[j].c-F[i].c)-(j-i)*s; if(temp>0&&F[j].gain<temp){ F[j].rep=i; F[j].gain=temp; } } } for (int i = 0; i < n; i += 1) { if (F[i].rep==i) { ans+=F[i].y*F[i].c; }else{ ans+=F[F[i].rep].c*F[i].y; ans+=(i-F[i].rep)*F[i].y*s; } } printf("%I64d\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