[HNOI2008]玩具装箱TOY

题目描述

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

输入输出格式

输入格式：

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

输出格式：

输出最小费用

输入输出样例

输入样例#1：

输出样例#1：

1

题解：
和上题一样的套路哈.直接写出原始dp方程，f[i]=f[j]+(sum[i]-sum[j]+i-j-L-1)^2
但是天真的小朋友，千万把后面一块全拆.分i，j两部分即可
变为f[i]=f[j]+((sum[i]+i-L-1)+(-j-sum[j]))^2 然后开平方
最后变为斜率优化的标准形式：
(f[j]-f[k]+(j+sum[j])^2-(k+sum[k])^2)/(2*((-k-sum[k])-(-j-sum[j])))<=(sum[i]+i-L-1)
那么(sum[i]+i-L+1)就是当前直线斜率，(f[j]-f[k]+(j+sum[j])^2-(k+sum[k])^2)就是y，(2*((-k-sum[k])-(-j-sum[j])))就是x.
直接维护凸壳即可 代码好写

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 typedef long long ll;
 9 const int N=50005;
10 ll sum[N];
11 int gi(){
12     int str=0;char ch=getchar();
13     while(ch>'9' || ch<'0')ch=getchar();
14     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
15     return str;
16 }
17 int n,m,q[N];ll f[N];
18 ll fy(int i,int j){
19     return f[i]+(i+sum[i])*(i+sum[i])-f[j]-(j+sum[j])*(j+sum[j]);
20 }
21 ll fx(int i,int j){
22     return ((-(-i-sum[i])+(-j-sum[j]))<<1);
23 }
24 void work(){
25     n=gi();m=gi();
26     for(int i=1,x;i<=n;i++)x=gi(),sum[i]=sum[i-1]+x;
27     int l=1,r=1,j,k;q[1]=0;
28     for(int i=1;i<=n;i++){
29         while(l<=r-1){
30             j=q[l];k=q[l+1];
31             if(fy(j,k)>=fx(j,k)*(sum[i]+i-m-1))l++;
32             else break;
33         }
34         f[i]=f[q[l]]+(sum[i]-sum[q[l]]+i-q[l]-1-m)*(sum[i]-sum[q[l]]+i-q[l]-1-m);
35         while(l<=r-1){
36             j=q[r];k=q[r-1];
37             if(fy(i,j)*fx(j,k)<=fx(i,j)*fy(j,k))r--;
38             else break;
39         }
40         q[++r]=i;
41     }
42     printf("%lld
",f[n]);
43 }
44 int main()
45 {
46     work();
47     return 0;
48 }

[HNOI2008]玩具装箱TOY

题目描述

输入输出格式

输入输出样例

相关推荐