[LuoguP3195] [HNOI2008]玩具装箱TOY

[HNOI2008]玩具装箱（Link）

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

简单来说，我们有一个长度为\(L\)的序列\(C[i]\),要求将序列分成若干段，每一段如果从\(i\)到\(j\)，整段的和为\(S\)，那么就会产生\((j-i+S-L)^2\)的代价，要求得到最小的代价和。
那么\(S\)就是\(\sum_{k=i}^{k<=j}C[k]\)，那么我们就可以把式子简化成这样：\(\sum_{k=i}^{k<=j}(C[k]+1)-(L+1)\)，所以你可以发现如果将输入的所有\(C[i]\)加上\(i\)并且将\(L\)全部加上\(1\)的话，费用就变成了\((S-L)^2\)。
设\(sum[i]\)为\(i\)点的前缀和，我们得到\(DP\)式子为\(f[i]=min_{j=0}^{j<=i}(f[j]+(sum[i]-sum[j]-L+i-j-1)^2)\)
嗯，按照上面的节奏，我们将\(j\)范围内的式子变一下：\(f[i]=min_{j=0}^{j<=i}(f[j]+((sum[i]+i)-(sum[j]+j)-L)^2)\)
然后我们令\(s[i]=sum[i]+i\)，式子就变成了这样：\(f[i]=min_{j=0}^{j<=i}(f[j]+(s[i]-s[j]-L)^2)\)
然后把里面的平方展开\(f[i]=min_{j=0}^{j<=i}(f[j]+s[i]^2+(s[j]+L)^2-2*s[i]*(s[j]+L))\)
然后稍微一个移项\(f[i]+2*s[i]*min_{j=0}^{j<=i}(s[j]+L)=f[j]+s[i]^2+(s[j]+L)^2\)
然后我们看这个式子的格式就很熟悉了

b+kx=y

对！就是前面搞的直线的解析式！所以我们知道这么一个转化

\(x=s[j]+L\)

\(y=f[j]+s[i]^2+(s[j]+L)^2\)

并且我们还知道\(dp[i]\)就是上面的\(y=kx+b\)的截距。那么我们将所有的\((x=s[j]+L，f[j]+s[i]^2+(s[j]+L)^2)\)点全部加到平面直角坐标系上，然后维护下凸壳就可以啦！并且你可以发现斜率\(k=2*s[i]\)是一个单调递增的哦~
并且这里还有一个很重要的地方：大家看上面的那个\(y\)的方程是\(y=f[j]+s[i]^2+(s[j]+L)^2\)而实际上这里并不是一个关于\(i,j\)的双变量，我们
至于凸壳的寻找方法和最优点的寻找方法上面已经有比较详细的介绍了，就不再多说，上代码讲解就好了吧。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100010
#define INF 0x7fffffff
#define ll long long
using namespace std;
ll n,L,s[MAXN],f[MAXN];
ll q[MAXN],head,tail;
inline void read(ll &x){
    char c=getchar(); x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c<='9'&&c>='0') x=x*10+c-48,c=getchar();
}
inline void print(ll x){
    ll num=0; char c[15];
    while(x) c[++num]=(x%10)+48,x/=10;
    while(num) putchar(c[num--]);
    putchar('\n');
}
inline double x(ll j){
    return s[j];
}
inline double y(ll i){
    return f[i]+(s[i]+L-1)*(s[i]+L-1);
}
inline double slope(ll i,ll j){
    return (y(j)-y(i))/(x(j)-x(i));
}
int main(){
    read(n); read(L);
    L++; head=1; tail=1;
    for(int i=1;i<=n;i++){
        ll x;  read(x);
        s[i]=s[i-1]+x;
        s[i]+=i;
    }
    for(int i=1;i<=n;i++){
        while(head<tail&&slope(q[head],q[head+1])<2*s[i])
        head++;  ll j=q[head];
        f[i]=f[j]+(s[i]-s[j]-L)*(s[i]-s[j]-L);
        while(head<tail&&slope(q[tail-1],q[tail])>slope(q[tail],i))
            tail--;
        q[++tail]=i;
    }
    print(f[n]);
    return 0;
}

巴特西

[LuoguP3195] [HNOI2008]玩具装箱TOY

[HNOI2008]玩具装箱（Link）

\(x=s[j]+L\)

\(y=f[j]+s[i]^2+(s[j]+L)^2\)

最新文章

热门文章