SP15648 [APIO10A] - Commando 题解 - JustPureH2O 的博客

~~小星野战力那么强一个人一组就够了ᕕ(◠ڼ◠)ᕗ~~

Done

您已获得最佳的阅读体验！~~以及上面的小彩蛋……~~

我们会发现这道题和 P5785 任务安排长得神似。两道题都是把一个连续的序列分成若干块（块数没有特殊限制）。这启发我们把状态设置为 dp[i]，含义是：“把前个士兵全部分好的最大修正战斗力”。

现在我们着手设计一个暴力 DP 程序，分析如下图：

因为部分已知，就是我们的 dp[j]；我们重点需要解决的就是部分的计算。

考虑到题面行动队战斗力的定义涉及到部分元素的和，因此预先维护整个序列的前缀和，于是。把待求区间分成一组，初始战斗力就是。本题还涉及到一个“修正战斗力”，且题目要求求解修正战斗力的最大值，不妨令，那么该组的修正战斗力就是。

暴力 DP 代码就可以写出来了，时间复杂度。预计，就不放了。

看到题面的，正解的时间复杂度很可能是或的。暴力程序的性能瓶颈卡在变量的循环上，因此考虑优化的求解，此时就开始了本题的重头戏——斜率优化/凸包优化。

把需要最大化的算式拿出来分析，我们进行化简可以得到：

进行斜率优化时，我们把看作主元，并且希望让斜率仅和有关。那我们移项可以得到：

类比直线的斜截式方程，发现这个式子可以用数形结合的方式做出来：斜率，截距，纵坐标，横坐标。任务是最大化 dp[i] 的值，考虑到，所以只要构造的直线的截距最大，dp[i] 就是最大的。

对于特定斜率的直线，显然是靠上端的直线截距更大，如下图（若绘图有误烦请指出）：

对于不同斜率的点，截距最大的直线所过的点均在一个上凸包上（红线连出）：

同时，当前直线所过的点是第一个斜率比当前直线斜率小的点。“最小值最大”，那不就是二分嘛！别急，这道题可以不用二分，有更简便的方法。

考虑到每次代入的点，因为每个士兵的战斗力均为正数，显然它的前缀和不可能出现下降趋势，是单调递增的。又知道是递增枚举的，所以每次构造的直线的斜率是单调递减的。因此考虑用单调队列维护这个合法点，具体操作如下：

当队头点的斜率大于了当前直线的斜率，显然不会再被用到，直接弹出。形式化地，当时弹队头。
当队尾点的斜率小于将要加入的点的斜率，原先的队尾已经不满足上凸包“斜率单调递减”的要求了，故弹出。也就是说当时就弹出队尾。

至此，单调队列的队头就是我们所维护的。把代入状态转移方程里即可计算出答案了（注意超时的原因是暴力找，和状态转移方程本身没关系），由于涉及斜率的计算，要使用浮点数（或者你也可以就使用整型，斜率换成交叉相乘）。

代码：

1
#include <bits/stdc++.h>
2

3
#define N 1000010
4
using namespace std;
5

6
typedef long long ll;
7

8
double dp[N];
9
double x[N], sumX[N];
10
double a, b, c;
11
int q[N];
12
int hh = 0, tt = 0;
13

14
double getY(int i) {
15
    // 获得纵坐标的值
16
    return dp[i] + a * sumX[i] * sumX[i] - b * sumX[i];
17
}
18

19
double slope(int x1, int x2) {
20
    // 获取两点斜率
21
    return (getY(x1) - getY(x2)) * 1.0 / (sumX[x1] - sumX[x2]) * 1.0;
22
}
23

24
int main() {
25
    ios::sync_with_stdio(false);
26
    cin.tie(nullptr);
27
    cout.tie(nullptr);
28

29
    int n, t;
30
    cin >> t;
31
    while (t--) {
32
        // 多测清空
33
        memset(dp, 0, sizeof dp);
34
        memset(x, 0, sizeof x);
35
        memset(sumX, 0, sizeof sumX);
36
        hh = 0, tt = 0; // 初始时队列里已有一个元素0
37

38
        cin >> n >> a >> b >> c;
39
        for (int i = 1; i <= n; i++) {
40
            cin >> x[i];
41
            sumX[i] = sumX[i - 1] + x[i];       // 预处理前缀和
42
        }
43
        q[0] = 0;
44
        for (int i = 1; i <= n; i++) {
45
            while (hh < tt && slope(q[hh + 1], q[hh]) >= 2 * a * sumX[i]) hh++; // 不满足单调性，弹出
46
            int j = q[hh]; // 维护的点
47
            double X = sumX[i] - sumX[j]; // 我们定义的X，用来简化计算
48
            dp[i] = dp[j] + a * X * X + b * X + c; // 代入状态转移方程
49
            while (hh < tt && slope(q[tt], q[tt - 1]) <= slope(i, q[tt])) tt--; // 不满足上凸包性质，弹出
50
            q[++tt] = i; // 插入新点
51
        }
52
        cout << (ll) dp[n] << endl; // 注意转型成整型
53
    }
54
    return 0;
55
}

音乐

音乐

评论区

音乐

目录