【bzoj3437】【小p的牧场】【斜率优化dp】
发布日期:2021-11-16 15:38:16 浏览次数:4 分类:技术文章

本文共 1291 字,大约阅读时间需要 4 分钟。

Description


 背景

    小P是个特么喜欢玩MC的孩纸。。。

 描述

    小P在MC里有n个牧场,自西向东呈一字形排列(自西向东用1…n编号),于是他就烦恼了:为了控制这n个牧场,他需要在某些牧场上面建立控制站,每个牧场上只能建立一个控制站,每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场(它西边第一个控制站所在的牧场不被控制)(如果它西边不存在控制站,那么它控制西边所有的牧场),每个牧场被控制都需要一定的花费(毕竟在控制站到牧场间修建道路是需要资源的嘛~),而且该花费等于它到控制它的控制站之间的牧场数目(不包括自身,但包括控制站所在牧场)乘上该牧场的放养量,在第i个牧场建立控制站的花费是ai,每个牧场i的放养量是bi,理所当然,小P需要总花费最小,但是小P的智商有点不够用了,所以这个最小总花费就由你来算出啦。

Input

    第一行一个整数 n 表示牧场数目

    第二行包括n个整数,第i个整数表示ai

    第三行包括n个整数,第i个整数表示bi

 

Output

   只有一行,包括一个整数,表示最小花费

Sample Input

4
2424
3142

Sample Output


9

样例解释

选取牧场1,3,4建立控制站,最小费用为2+(2+1*1)+4=9。

数据范围与约定


对于100%的数据,1<=n<=1000000,0<ai,bi<=10000
题解:同bzoj1096.
代码:
#include
    
     #include
     
      #include
      
       #define N 1000010using namespace std;int q[N],n,l,r;long long s[N],a[N],p[N],sp[N],c[N],f[N];long long G(int a,int b){return f[b]-f[a]+sp[b]-sp[a];}long long S(int a,int b){return p[b]-p[a];}double work(int a,int b){return G(a,b)*1.0/S(a,b)*1.0;}int main(){   scanf("%d",&n);  for (int i=1;i<=n;i++) scanf("%lld",&c[i]);  for (int i=1;i<=n;i++) scanf("%lld",&a[i]);  for (int i=1;i<=n;i++) p[i]=p[i-1]+a[i];  s[1]=0;for (int i=2;i<=n;i++) s[i]=s[i-1]+1;  for (int i=1;i<=n;i++) sp[i]=sp[i-1]+s[i]*a[i];  for (int i=1;i<=n;i++){   while (l
       
        
         
while (l work(q[r],i)) r--;   q[++r]=i;  }  cout< <
 }



转载地址:https://blog.csdn.net/sunshinezff/article/details/50965952 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj2049】【SDOI2008】【洞穴勘测】【lct】
下一篇:【bzoj1010】【HNOI2008】【玩具装箱toy】【斜率优化】

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.172.111.71]2022年05月22日 09时45分50秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章