注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2153]设计铁路  

2014-12-01 19:41:20|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2153: 设计铁路

Time Limit: 5 Sec  Memory Limit: 259 MB
Submit: 114  Solved: 80
[Submit][Status]

Description

A 省有一条东西向的公路经常堵车,为解决这一问题,省政府对此展开了调查。调查后得知,这条公路两侧有很多村落,每个村落里都住着很多个信仰c教的教徒,每 周日都会开着自家的车沿公路到B地去“膜拜”他们的教主,这便是堵车的原因。详细调查显示:这里总共有N个村落,并且它们都在B地的东边。编号为i的村落 住有Ri个信仰c教的教徒,距离B地的距离为Ti(单位:公里)。为解决这一问题,A省政府决定在这条公路下修建一条地下快速铁路来缓解交通,并沿线修建 若干个车站(B地会修建终点站,不算车站)。每名教徒都会先往B地方向开车(如果他所在村庄处恰好有车站就不必开车了),到最近的一个快速铁路车站时换乘 (如果直接开到B地就不用换乘了),再通过快速铁路到B地。但A政府遇到一个难题:修建多少个车站以及在哪修建车站。一个修建车站的方案中,如果修建过多 的车站则会花费过多的钱,但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A政府为了协调这两方面,采用评分的方式来衡量一个方案的好坏(分数越 大方案越坏):每修建一个车站会增加m的分数,在某一次“膜拜”中(只考虑去,不考虑返回),每导致1个教徒开车行驶1公里会增加1分。现请你设计一个修 建车站的方案,使得分数最小。请输出这个最小的分数。

Input

输入的第一行包含两个正整数n、m。之后n行每行两个正整数Ti、Ri。

Output

输出一个整数,表示最小的分数。

Sample Input

【样例输入1】
4 20
25 3
5 3
25 2
20 5
【样例输入2】
4 30
25 3
5 3
25 2
20 5

Sample Output

【样例输出1】
55

【样例输出2】
70
【样例说明】
样例1中,在距B地20km处和距B地25km处修建车站,1、3、4号村落里的教徒就不必开车了,得分20*2=40分。2号村落里的教徒直接开车到B地,得分3*5=15分。总共得分55分。
样例2中,在距B地20km处修建车站,4号村落里的教徒就不必开车了,得分30分。1号和3号村落里的教徒先开车到距B地20km处的车站,得分3*5+2*5=25分。2号村落里的教徒直接开车到B地,得分3*5=15分。总共得分70分。
【数据规模】
对于100%的数据,n<=40000,m<=2000000000,Ti<=1000000,Ri<=1000。
提示:请注意使用64位整型存储某些数据和结果。

Solution

一眼斜率优化但是写搓了233

cnt表示前缀和,sum表示权值前缀和。从后往前做。

f[i]=m+min(f[j+1]+sum[j]-sum[i]-i*(cnt[j]-cnt[i]))

直接套模版吧

两个不等号的方向反正只有4种情况,跟暴力无脑拍一下就好了,哪个对就是哪个

Code

/**************************************************************
    Problem: 2153
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2472 ms
    Memory:43780 kb
****************************************************************/
 
#include<cstdio>
const int N=1000010;
int n,m,x,z,i,j,max,l,r,q[N];
long long sum[N],cnt[N],f[N],t[N],y[N];
long long min(long long a,long long b){return a<b?a:b;}
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d",&x,&z),t[x]+=z,max<x?max=x:1;
    for(i=1;i<=max;i++)sum[i]=sum[i-1]+t[i]*i,cnt[i]=cnt[i-1]+t[i];
    f[max]=m;q[l=r=1]=max;y[max]=f[max+1]+sum[max];
    for(i=max-1;~i;i--)
    {
        while(l<r&&y[q[l+1]]-y[q[l]]<i*(cnt[q[l+1]]-cnt[q[l]]))l++;
        f[i]=m+f[q[l]+1]+sum[q[l]]-sum[i]-1LL*i*(cnt[q[l]]-cnt[i]);y[i]=f[i+1]+sum[i];
        while(l<r&&(y[q[r]]-y[q[r-1]])*(cnt[i]-cnt[q[r]])<=(y[i]-y[q[r]])*(cnt[q[r]]-cnt[q[r-1]]))r--;
        q[++r]=i;
    }
    printf("%lld\n",f[0]-m);
}
  评论这张
 
阅读(187)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018