10188. 「一本通 5.6 练习 1」玩具装箱

Link

题意

你可以将一段连续的玩具扔到同一个容器中,如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中,则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(X-L)^2$,其中 $L$ 是一个常量。
求最小花费。
对于全部数据,$1\le N\le 5\times 10^4,1\le L,C_i\le 10^7$。

思路

首先,考虑$dp$。
设$f[i]$表示前$i$个玩具的最小花费,那么最终的答案就是$f[n]$。
那么很容易就可以得知:$f[i]=min(f[j]+(i-j+\sum_{k=i}^{j}C_k-L-1)^2)(1\leq j <i,1\leq i\leq n)$
考虑优化。

优化1

设$sum[i]$表示$C$数组的前缀和,那么转移方程可化为:$f[i]=min(f[j]+(i-j-sum[j]+sum[i]-L-1)^2)(1<=i<=n,1<=j<i)$
时间复杂度:$O(N^3)–>O(N^2)$
预计得分:20pt

优化2

考虑斜率优化。
原转移方程可化为:$f[i]=f[j]+(i+sum[i]-L-1-sum[j]-j)^2$
设$A[i]=sum[i]+i$,$B[i]=sum[i]+i-L-1$
则$f[i]=f[j]+(A[i]-B[j])^2$,
$f[i]=f[j]+A[i]^2+B[j]^2-2\times A[i]\times B[j]$,
$2\times A[i]\times B[j]+f[i]-A[i]^2=f[j]+B[j]^2$。
设$x=B[j],y=f[j]+B[j]^2$,
那么$y=x\times (2\times A[i])+(f[i]-A[i]^2),slope=2\times A[i]$。
$f[i]=y+A[i]^2-2\times A[i]\times x$。
那么就斜率优化鸭。


Code

#include<bits/stdc++.h>
#define int long long
#define sqrs(x) ((x)*(x))
#define A(i) ((sum[i])+(i))
#define B(i) ((sum[i])+(i)+(L)+(1))
#define X(j) (B(j))
#define Y(j) ((f[j])+sqrs(B(j)))
#define slope(i,j) (double)((double)(Y(i)-Y(j))/(double)(X(i)-X(j)))
#define Slope(i) (2*(A(i)))
#define solve(i,j) (f[j]+sqrs(i-j-sum[j]+sum[i]-L-1))
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int zx){
    if(zx<0) putchar('-'),zx=-zx;
    if(zx<10) putchar(zx+'0');
    else{
        write(zx/10);
        putchar(zx%10+'0');
    }
}
int n,L,sum[50010],f[50010],q[50010],h,t;
signed main(){
    n=read();L=read();
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
    memset(f,63,sizeof(f));
    f[0]=0;h=t=1;
    for(int i=1;i<=n;i++){
        while(h<t&&slope(q[h],q[h+1])<Slope(i)) h++;
        f[i]=f[q[h]]+sqrs(A(i)-B(q[h]));
        while(h<t&&slope(q[t-1],q[t])>slope(i,q[t-1])) t--;
        q[++t]=i;
    }
    write(f[n]);putchar('\n');
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇