首页 > 代码库 > BZOJ 2153 设计铁路
BZOJ 2153 设计铁路
裸的斜率优化。
(我为什么要O(1e6)。。。)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000050 using namespace std; long long n,m,t,r,sum1[maxn],sum2[maxn],f[maxn],mx=0,q[maxn],l=1; long long get_x(long long x) {return x;} long long get_y(long long x) { if (!x) return 0; return f[x-1]-sum1[x-1]+sum2[x-1]*x+m; } int main() { scanf("%lld%lld",&n,&m); for (long long i=1;i<=n;i++) { scanf("%lld%lld",&t,&r); mx=max(mx,t);sum1[t]+=r*t;sum2[t]+=r; } for (long long i=1;i<=mx;i++) sum1[i]+=sum1[i-1],sum2[i]+=sum2[i-1]; q[l=r=1]=0; for (long long i=1;i<=mx;i++) { while (l<r && (get_x(q[r-1])-get_x(q[r]))*(get_y(q[r])-get_y(i))<(get_x(q[r])-get_x(i))*(get_y(q[r-1])-get_y(q[r]))) r--; q[++r]=i; while (l<r && sum2[i]*(get_x(q[l])-get_x(q[l+1]))<(get_y(q[l])-get_y(q[l+1]))) l++; f[i]=get_y(q[l])-q[l]*sum2[i]+sum1[i];f[i]=min(f[i],sum1[i]); } printf("%lld\n",f[mx]); return 0; }
BZOJ 2153 设计铁路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。