提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

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

练习 5.6 一本 玩具 装箱
2023-06-13 09:12:49 时间

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

题意

你可以将一段连续的玩具扔到同一个容器中，如果要将 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)

优化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;
}

相关文章