洛谷P3195 玩具装箱 题解报告

题目地址

题意：

如题所述。

分析：

斜率优化dp模板题。

题目没看清就下手，自以为题面所述中 i > j；原始dp式子也没设计准确。

中途在错误方向上头铁时，甚至没注意到横坐标是沿负轴增长的。

思路

\(x=i-(j+1)+s_i-s_j\ (i>j)\)

令\(h=s_i+i,\ g=j+1+s_j\)，则\(x=h-g\)。

对于dp原式：

\(dp[i]=min(dp[j]+(x-L)^2)\)
$ =min(dp[j]+g^2 +2Lg-2hg)+(h-L)^2$

令:

$ x=g,\ \ y=dp[i]+2Lg+g^2 ,\ \ k=2h,\ \ b=dp[i]-(h-L)^2 $

原式转换为\(b=min(y-kx)\)。也就是在k为给定值的情况下，去寻找小截距值。

由于是找最小值，用单调栈维护下凸包，每次用斜率为正的直线切，找到最优点，从最小截距值中获得dp[i]。

上次用了单调队列，这次就用二分查找吧，复杂度\(O(nlogn)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e4+5;

ll dp[maxn];
struct Pos{
    ll x,y;
} st[maxn];

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    int n;
    ll L;
    cin>>n>>L;
    ll s=0; //前缀和
    int up=1;
    st[1]={1,2*L+1};
    for(int i=1;i<=n;++i)
    {
        ll t,x,y;
        cin>>t;
        s+=t;
        ll k =2*(s+i);
        int l=0,r=up;
        while(r-l!=1)
        {
            int m=(r+l)/2;
            if(st[m+1].y-st[m].y<k*(st[m+1].x-st[m].x))
                l=m;
            else
                r=m;
        }
        dp[i]=st[r].y-k*st[r].x+(s+i-L)*(s+i-L);
        x=i+1+s;
        y=dp[i]+2*L*x+x*x;
        while(up>1 && (st[up].y-st[up-1].y)*(x-st[up].x)>(y-st[up].y)*(st[up].x-st[up-1].x))
            --up;
        st[++up]={x,y};
    }
    cout<<dp[n];
}