「Bzoj 1911」「Apio2010」特别行动队 (最大化斜率优化DP)

发表于 | 分类于 | | + s

BZOJ 1911
题意：有$n$个数$x_i$，将其分成连续的组，每组的分为$a\sum x_i + b\sum x_i +c$，求最大的总分。
设$dp(i)$为前$i$个分组的最大的总分。设$\operatorname{sum}(n)$为$\sum\limits_{i=1}^n x_i$
则
$$
dp(i)=\max(dp(j)+a[\operatorname{sum}(i)-\operatorname{sum}(j)]^2 + b[\operatorname{sum}(i)-\operatorname{sum}(j)] + c)
$$
则决策点可以表示为点$(\operatorname{sum}(j), dp(j)+a \cdot \operatorname{sum}(j)^2 - b \cdot \operatorname{sum}(j))​$

这里要维护最大值，所以与之前的斜率优化不同，维护一个上凸包即可。

注意有负数时不要用叉积，符号不能确定！

知识点
1、有负数时不要用叉积，符号不能确定

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 1000000 + 5;

    LL n, x[MAXN], a, b, c, s[MAXN];
    LL dp[MAXN], q[MAXN];

    LL getx(LL j) {return s[j];}
    LL gety(LL j) {return dp[j] + a * s[j] * s[j] - b * s[j];}
    db slp(LL i, LL j) {
        return 1.0 * (gety(j) - gety(i)) / (getx(j) - getx(i));
    }

    void clean() {
        ms(s, 0), ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n >> a >> b >> c;
        for (LL i = 1; i <= n; ++i) scanf("%lld", &x[i]), s[i] = s[i - 1] + x[i];

        LL l = 1, r = 1;
        q[l] = 0;
        for (LL i = 1; i <= n; ++i) {
            /*while (l < r && (gety(q[l + 1]) - gety(q[l])) >= 2 * a * s[i] * (getx(q[l + 1]) - getx(q[l]))) ++l;
            dp[i] = dp[q[l]] + a * (s[i] - s[q[l]]) * (s[i] - s[q[l]]) + b * (s[i] - s[q[l]]) + c;
            while (l < r && (gety(q[r]) - gety(q[r - 1])) * (getx(i) - getx(q[r])) <= (getx(q[r]) - getx(q[r - 1])) * (gety(i) - getx(q[r]))) --r;
            q[++r] = i;*/
            while (l < r && slp(q[l], q[l + 1]) >= 2.0 * a * s[i]) ++l;
            dp[i] = dp[q[l]] + a * (s[i] - s[q[l]]) * (s[i] - s[q[l]]) + b * (s[i] - s[q[l]]) + c;
            while (l < r && slp(q[r - 1], q[r]) <= slp(q[r], i)) --r;
            q[++r] = i;
            // 有负数不要用叉积，符号不能确定 
        }

        cout << dp[n];

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------