bzoj1010&luogu3195 [HNOI2008]玩具装箱TOY

bzoj1010&luogu3195 [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：

5 4 3 4 2 1 4

输出样例#1：

1

首先考虑朴素的方程 f[i]=min(f[j]+cost[i][j]) 复杂度n^2 j每次从1~i枚举 相当于一个前缀 所以是斜率优化的套路 同时推算式子满足决策单调性 于是可以斜率优化

这题的cost非常不好算 在zhx大佬的指引下 我们因为必须要有填充物 所以不妨做的时候我们就给每个物品提前把填充物写进去 然后做个前缀和即 g[i]=c[1]+c[2]+…c[i]+1+2+…i; 然后推导公式的时候发现最后还需要多－1 我们干脆把这个-1 放在L里即可

可以上来先考虑斜率优化的套路 设k1 < k2那么可以猜想当k2优于k1时 k1这个决策就失去了他的作用 记f[k1]为在k1这个点时我们花费的最小代价 即根据假设有式子 设k1 < k2

f[k2]+(g[i]-g[k2]-L)^2< f[k1]+(g[i]-g[k1]-L)^2

两边平方打开 f[k2]-2*g[i]*g[k2]+2*L*g[k2]< f[k1]-2*g[i]*g[k1]+2*L*g[k1]

(f[k2]-f[k1]+2*L*(g[k2]-g[k1]))/2*(g[k2]-g[k1]) < g[i]

验证我们是否决策单调 设t>i那么g[i]一定< g[t] 所以因为只要满足这个式子 我就可以推出k2优于k1所以 满足 当我们g[i]>这个斜率的时候我的k1这个决策就可以抛弃了 同时 在新加入的时候 如果我末尾的决策不满足斜率的单调性 我就先将他们弹出 直到满足 再入队

因为当我slope(r-1,r)不< g[i]之时说明我的r-1 不可能再满足条件了 如果 这时候我的slope(r,i)比slope(r-1,r)还小 所以我的r更不可能是答案了 直接扔掉

#include#define N 55000#define ll long longinline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}long long g[ N],f[N];int n,L,q[N];inline double slope(int k2,int k1){ return (f[k1]-f[k2]+g[k1]*g[k1]-g[k2]*g[k2]+2*L*(g[k1]-g[k2]))/(2.0*(g[k1]-g[k2]));}int main(){ freopen("3195.in","r",stdin); n=read();L=read();L+=1; for (int i=1;i<=n;++i) g[i]=read(),g[i]+=g[i-1]; for (int i=1;i<=n;++i) g[i]+=i; int l=1,r=0;q[++r]=0; for (int i=1;i<=n;++i){ while (l

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。