Chlience

【题解】BZOJ 1010 玩具装箱Toy
Problem略Thought状态转移方程:(显然)我们以$Slope(x,y)$来表示上面那个类似于斜率的东西(...
扫描右侧二维码阅读全文
14
2018/11

【题解】BZOJ 1010 玩具装箱Toy

Problem

Thought

状态转移方程:(显然)

$$ dp[i]=min(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2) $$

$sum$为前缀和
然后我们令$f[i]=sum[i]+i,c=1+L$
原式可以化简为:

$$ dp[i]=min(dp[j]+(f[i]-f[j]-c)^2) $$

注意,这里的$f,c$都是可以预处理出来的

1.证明决策单调性

假设在当前由$j$状态转移优于$k$状态(显然$k$是之前枚举的决策),即:

$$ dp[j]+(f[i]-f[j]-c)^2\le dp[k]+(f[i]-f[j]-c)^2 $$

那么对于$i$后面的一个状态$t$,要保证$k$对其无贡献(已经被$j$覆盖)
则需要证明:

$$ dp[j]+(f[t]-f[j]-c)^2\le dp[k]+(f[t]-f[k]-c)^2 $$

由于$f[i]=sum[i]+i$,所以一定为单调递增的($sum$和$i$均为单调递增)
所以令$v=f[t]-f[i]$
原式可化为:

$$ dp[j]+(f[i]+v-f[j]-c)^2\le dp[k]+(f[i]+v-f[k]-c)^2 $$

变形,尽量拆出已有的式子

$$ dp[j]+(f[i]-f[j]-c)^2+2v*(f[i]-f[j]-c)+4v^2\le dp[k]+(f[i]-f[k]-c)^2+2v*(f[i]-f[k]-c)+4v^2 $$

移项,消除相同项

$$ f[i]-f[j]-c\le f[i]-f[k]-c\\ f[j]\ge f[k] $$

由单调递增性,只需要枚举状态时以$1$~$i-1$的顺序即可保证$f[j]\ge f[k]$,得证

2.求斜率方程

当前决策$i$,若由$j$状态转移优于$k$状态,则有:

$$ dp[j]+(f[i]-f[j]-c)^2\le dp[k]+(f[i]-f[j]-c)^2 $$

展开,变形,得:

$$ dp[j]+f[i]^2-2f[i]* (f[j]+c)+(f[j]+c)^2\le dp[k]+f[i]^2-2f[i]* (f[k]+c)+(f[k]+c)^2 $$

移项,消除相同项,尽量将变量按$j,k$凑在一起,得:

$$ \frac {(dp[j]+(f[j]+c)^2)-(dp[k]+(f[k]+c)^2)}{2*(f[j]-f[k])}\le f[i] $$

左边部分就像斜率一样,可以看做:

$$ \frac {Y_j-Y_k} {X_j-X_k} $$

我们以$Slope(x,y)$来表示上面那个类似于斜率的东西(其实就是斜率好么)
若满足这个$Slope(k,j)\le f[i]$,则说明$j$比$k$优

3.组织算法

那么对于当前较优的状态我们建立一个队列$q$
维护这个队列我们有以下操作:

  1. 若$Slope(q[l],q[l+1])\le f[i]$,则$q[l]$没有$q[l+1]$优,则删除$q[l]$
  2. 若$Slope(q[r-1],q[r])\ge Slope(q[r],i)$,则删除$q[r]$

分析:

方程成立时是$j$比$k$优的充分必要条件,那么假设我们现在有一个序列,那么队头就是当前最优的,若到了某个$i$值使得对于队首$p[l]$和队次首$p[l+1]$来说$Slope(q[l],q[l+1])\le f[i]$成立,则$q[l+1]$比$q[l]$优,所以弹出队首,直到不成立为止

第一条操作是显然的,那么第二条呢?

一个状态要不要放在序列里,是由它能不能做出贡献决定的,也就是说,它能不能成为队首决定的

假设我们现在有$Slope(q[a],q[a+1])\ge Slope(q[a+1],q[a+2])$,那么,$q[a+1]$点想要成为队首就只能当前面的点都弹出了,并且$Slope(q[a],q[a+1])\le f[i]$,$q[a+1]$比$q[a]$优所以也将$q[a]$弹出时,才能成为队首。但是在这时,由于$f[i]\ge Slope(q[a],q[a+1])\ge Slope(q[a+1],q[a+2])$,那么$q[a+2]$也应该比$q[a+1]$优,所以将$q[a+1]$弹出,意思就是,无论怎样,$q[a+1]$都不可能做出贡献
类比一下,我们只操作队尾时,若其斜率$Slope(q[r-1],q[r])\ge Slope(q[r],i)$,直接弹出$q[r]$即可

那么,在我们的这个操作以后,能够保证斜率单调递增,也就是维护一个上凸包,每次取队首作为答案即可

Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,L;
ll f[50005];
ll dp[50005];
ll q[50005];
ll head,tail; 
ll read() {
    ll ans=0,flag=1;
    char ch=getchar();
    while((ch<'0'||ch>'9') && ch!='-') ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
double slope(ll k,ll j) {return (double) (dp[j]-dp[k]+(f[j]+L)*(f[j]+L)-(f[k]+L)*(f[k]+L))/(2.0*(f[j]-f[k]));}
int main() {
    n=read(),L=read();
    L++;
    for(int i=1;i<=n;i++) {
        ll a=read();
        f[i]=f[i-1]+a+1;
    }
    for(int i=1;i<=n;i++) {
        while(head<tail && slope(q[head],q[head+1])<=f[i]) head++;
        int t=q[head];
        dp[i]=dp[t]+(f[i]-f[t]-L)*(f[i]-f[t]-L);
        while(head<tail && slope(q[tail],i)<slope(q[tail-1],q[tail])) tail--;
        q[++tail]=i;
    } 
    printf("%lld",dp[n]);
}
Last modification:March 5th, 2019 at 05:20 pm

Leave a Comment