Luogu P3195 [HNOI2008]玩具装箱

题目描述

https://www.luogu.com.cn/problem/P3195

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个正整数 $L$，现在需要将这个序列划分成若干连续段，对于 $[l,r]$ 这一段，其长度定义为 $len=r-l+\sum_{i=l}^ra_i$，其代价为 $(len-L)^2$，求最小代价和

$n\le 5\times 10^4$

Solution

容易得到朴素 $dp$ 为 $f_i = max\{f_j+(i-j+1-L+s_i-s_j)^2\}$

由于某种神秘力量，我们得知 $f$ 的转移满足决策单调性

且 $w_{x,y}$ 可以 $O(1)$ 计算，所以我们直接使用单调栈来进行决策单调性优化即可

时间复杂度 $O(n\log n)$

#include <iostream>
#include <deque>
#define maxn 50010
#define ll long long
#define INF 100000000000000000
using namespace std;

int n, L, a[maxn];
ll s[maxn];

inline ll F(ll x) { return x * x; } 

ll f[maxn];
inline ll w(int x, int y) { return x >= y ? INF : f[x] + F(y - x - 1 + s[y] - s[x] - L); }

struct node {
    int l, r, k;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n >> L;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];
    deque<node> Q; Q.push_back({ 1, n, 0 });
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front().r < i) Q.pop_front();
        f[i] = w(Q.front().k, i);
        while (!Q.empty() && w(Q.back().k, Q.back().l) >= w(i, Q.back().l)) Q.pop_back();
        int l = Q.back().l, r = Q.back().r, k = Q.back().k, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            if (w(k, mid) < w(i, mid)) ans = mid, l = mid + 1; 
            else r = mid - 1; 
        } Q.back().r = ans; if (ans < n) Q.push_back({ ans + 1, n, i });
    } cout << f[n] << endl; 
    return 0;
}