P3195 [HNOI2008]玩具装箱TOY(斜率优化）

题目描述

P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为 $C_iCi .为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第 ii 件玩具到第 jj 个玩具放到一个容器中，那么容器的长度将为 x=j-i+sumlimits_{k=i}^{j}C_kx=j−i+k=i∑jCk 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 xx ,其制作费用为 (X-L)^2(X−L)2 .其中 LL 是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 LL 。但他希望费用最小.$

感谢@ACの666 提供的Latex题面

输入输出格式

输入格式：

第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

输出格式：

输出最小费用

输入输出样例

输入样例#1：复制

输出样例#1：复制

 1 #include "bits/stdc++.h"
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 ll s[600000],f[600000],q[600000];
 7 ll n,m;
 8 
 9 ll y(ll x)
10 {
11     return x+s[x];
12 }
13 
14 ll  slope(ll j, ll k)
15 {
16     //return f[j]+(ll)(pow(y(j)+1+m,2)) - (f[k]+(ll)pow(y(k)+1+m,2)     );
17     return f[j]+(ll)pow(y(j),2)+2*(1+m)*y(j) - (f[k]+(ll)pow(y(k),2)+2*(1+m)*y(k) ) ;
18     
19 }
20 ll down(ll j,ll k)
21 {
22     return (2*y(j)-2*y(k));
23 }
24 
25 
26 
27 int main()
28 {
29     while (cin>>n>>m)
30     {
31         for (int i=1;i<=n;i++)
32         { 
33             ll x;cin>>x;s[i]=s[i-1]+x;
34         }
35         int L=1,R=1;
36         q[1]=f[0]=0; 
37         for (int i=1;i<=n;i++)
38         {
39             while (L<R&&slope(q[L+1],q[L])<=y(i)*down(q[L+1],q[L]))L++;
40             
41             int t=q[L];
42             
43             /*f[i]=f[t]+(ll)(pow(y(t),2))+1LL*2*(1+m)*y(t)
44             -1ll*2*y(t)*y(i)+(ll)pow(y(i),2)-1ll*2*(1+m)*y(i)+1LL*(1+m)*(1+m);
45             */ // 这么写就wa了，不知道为什么 
46             
47             f[i]=f[t]+(ll)pow(y(i)-y(t)-1-m,2);
48             
49             
50             while(L<R&&slope(q[R],q[R-1])*down(i,q[R])>=down(q[R],q[R-1])*slope(i,q[R]))R--;
51 
52             q[++R]=i;
53         }
54         cout<<f[n]<<endl;
55     }
56     
57 }