题解 P3195 【[HNOI2008]玩具装箱TOY】

League丶翎 · 2018-01-18 21:13:37 · 题解

顺手安利一波博客->Chlience

欢迎dalao交换友链

分析：

状态转移方程：（显然）

原式可以化简为：

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

1.证明决策单调性

假设在当前由j状态转移优于k状态（显然k是之前枚举的决策），即：

那么对于i后面的一个状态t，要保证k对其无贡献（已经被j覆盖）

则需要证明：

由于f[i]=sum[i]+i，所以一定为单调递增的（sum和i均为单调递增）

所以令v=f[t]-f[i]

原式可化为：

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

移项，消除相同项

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

2.求斜率方程

当前决策i，若由j状态转移优于k状态，则有：

展开，变形，得：

移项，消除相同项，尽量将变量按j,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]);
}