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 |
第一道斜率优化,纪念!#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> using namespace std; const int maxn=10000+10; int n,s,tt[maxn],f[maxn]; double sumt[maxn]; int dp[maxn],q[maxn],sumf[maxn]; int head,t; void headdelete(int i){ while (head<t&&(dp[q[head+1]]-dp[q[head]])/(sumt[q[head]-1]-sumt[q[head+1]-1])<=sumf[i]) head++; //不能写<=!!!!!! } void taildelete(int i){ while (head<t&&(dp[i]-dp[q[t]])/(sumt[q[t]-1]-sumt[i-1])<=(dp[q[t]]-dp[q[t-1]])/(sumt[q[t-1]-1]-sumt[q[t]-1])) t--; q[++t]=i; } int main() { scanf("%d%d",&n,&s); for (int i=1;i<=n;++i) { scanf("%d%d",&tt[i],&f[i]); sumt[i]=sumt[i-1]+tt[i]; } for (int i=n;i>=1;--i) sumf[i]=sumf[i+1]+f[i]; dp[n+1]=0; q[1]=n+1; head=1; t=1; for (int i=n;i>=1;--i){ headdelete(i); dp[i]=dp[q[head]]+(s+sumt[q[head]-1]-sumt[i-1])*sumf[i]; taildelete(i); } printf("%d",dp[1]); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator