关于 F 的斜率优化 DP

CSDN版本

把 sum 初始化写错了找了恁久错。。。

Solution

把题中 的定义改为 ，即令 ，如下式所示，其中 ，表示 的前缀和

再令 ，化简得

设 表示将前 个数分为 段的最小值。

考虑其转移

根据斜率优化 ，我们将纯变量放到左边称为 ，将带有“临时常量”系数的放到右边称为 ，最终得到（这里默认是依赖于上一维，所以省略 和 ）

上式中，有如下对应关系

对于 这条直线，我们最终要的就是截距 最小，而且这里随着 增加， 严格增加，所以维护一个关于 点对的下凸包即可。

对于 ，从下往上逼近凸包的直线斜率为 ，当这条直线第一次碰到凸包上的点，截距就是最小的。

我们可以用单调队列维护这个凸包，即对于凸包最左侧的两个相邻点产生直线的斜率 ，若 ，就将凸包最左侧的点弹出，这样能保证队头一定是最优的。

而要把第 个点插入队尾，就要求 与凸包最右侧的点产生的斜率 ，严格大于凸包最右侧两点产生的斜率 （这是根据下凸包的定义来的），如下图所示（图片来源）

在这里，斜率 的计算公式为 。

最后一点是，每次更新的时候， 的范围其实是 ，因为少于 个数一定不可能被分为 段，这样可以节省一半计算量。

时间复杂度 。

C++ Code

#include <bits/stdc++.h>

using i64 = int64_t;
using u64 = uint64_t;
using f64 = double_t;
using i128 = __int128_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cout << std::fixed << std::setprecision(12);
	
    int n, m, k;
    std::cin >> n >> m >> k;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
    	std::cin >> a[i];
    }
    std::vector<int> s(n + 1);
    for (int i = 0; i < n; i++) {
    	s[i + 1] = s[i] + a[i];
    }
    std::vector<int> x(n + 1);
    for (int i = 1; i <= n; i++) {
    	x[i] = s[i] + i * (i + 1) / 2;
    }

    std::vector<int> q(n + 1);
    std::vector<i64> dp(n + 1), ndp(n + 1);
    for (int i = 1; i <= n; i++) {
    	dp[i] = 1LL * (x[i] + k) * (x[i] + k);
    }
    std::vector<i64> y(n + 1);
    for (int i = 1; i <= n; i++) {
        y[i] = dp[i] + 1LL * x[i] * x[i];
    }
    for (int c = 2; c <= m; c++) {
    	int hh = 0, tt = 0;
        q[tt++] = c - 1;
    	for (int i = c; i <= n; i++) {
            int coef = x[i] + k;
    		while (hh + 1 < tt and (y[q[hh + 1]] - y[q[hh]]) <= (x[q[hh + 1]] - x[q[hh]]) * 2LL * coef) {
    			hh++;
    		}
    		int j = q[hh];
    		ndp[i] = dp[j] + 1LL * coef * coef + 1LL * x[j] * x[j] - 2LL * coef * x[j];
    		while (hh + 1 < tt and i128(y[i] - y[q[tt - 1]]) * (x[q[tt - 1]] - x[q[tt - 2]]) <= i128(y[q[tt - 1]] - y[q[tt - 2]]) * (x[i] - x[q[tt - 1]])) {
    			--tt;
    		}
    		q[tt++] = i;
    	}
    	for (int i = c; i <= n; i++) {
    		y[i] = ndp[i] + 1LL * x[i] * x[i];
    	}
    	dp.swap(ndp);
    }
    std::cout << dp[n] << "\n";

    return 0;
}