HDU3507:Print Article(斜率优化dp)

传送门

题意:
现有(n)个数,每个数的值为(a_i),现在可以把数划分为多段,每一段的代价为((sum_{k=i}^{j}c_i)^2+M)
问怎么划分,代价最小。

思路:
考虑dp,那么dp式子很简单:

[dp(i)=min{dp(j)+(S_i-S_j)^2+M} ]

注意这种(dp)形式,后面加上的部分与(i,j)两个变量有关,这种一般可以考虑分离变量然后斜率dp优化。
(PS.如果可以分为多个部分,每个部分只和一个有关,那么可以考虑单调队列优化。from进阶指南)
那么就尝试写成直线形式:

[dp_j+S_j^2=2S_iS_j+dp_i-S_i^2-M ]

这里我们以((S_j,dp_j+S_j^2))为一个点,然后用队列维护一个下凸壳就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005, MOD = 1e9 + 7;
int n, m;
ll sum[N], dp[N];
int a[N], q[N];
int main() {
#ifdef heyuhhh
    freopen("input.in", "r", stdin);
#else
    ios::sync_with_stdio(false); cin.tie(0);
#endif
    while(cin >> n >> m) {
        for(int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
        dp[0] = 0;
        int l = 1, r = 1;
        q[1] = 0;
        auto f = [&](int i) {
            return dp[i] + sum[i] * sum[i];
        };
        for(int i = 1; i <= n; i++) {
            while(l < r && f(q[l + 1]) - f(q[l]) <= 2 * sum[i] * (sum[q[l + 1]] - sum[q[l]])) ++l;
            dp[i] = dp[q[l]] + (sum[i] - sum[q[l]]) * (sum[i] - sum[q[l]]) + m;
            while(l < r && (f(i) - f(q[r])) * (sum[q[r]] - sum[q[r - 1]]) <= (f(q[r]) - f(q[r - 1])) * (sum[i] - sum[q[r]])) --r;
            q[++r] = i;
        }
        cout << dp[n] << '
';
    }
    return 0;
}
原文地址:https://www.cnblogs.com/heyuhhh/p/11415306.html