小星野战力那么强一个人一组就够了ᕕ(◠ڼ◠)ᕗ
您已获得最佳的阅读体验！以及上面的小彩蛋……
我们会发现这道题和 P5785 任务安排
长得神似。两道题都是把一个连续的序列分成若干块（块数没有特殊限制）。这启发我们把状态设置为
dp[i]，含义是：“把前
个士兵全部分好的最大修正战斗力”。
现在我们着手设计一个暴力 DP 程序，分析如下图：
因为 部分已知，就是我们的
dp[j]；我们重点需要解决的就是 部分的计算。
考虑到题面行动队战斗力的定义涉及到部分元素的和，因此预先维护整个序列的前缀和
，于是 。把待求区间分成一组，初始战斗力就是
。本题还涉及到一个“修正战斗力”，且题目要求求解修正战斗力的最大值，不妨令
，那么该组的修正战斗力就是
。
暴力 DP 代码就可以写出来了，时间复杂度 。预计 ，就不放了。
看到题面的 ，正解的时间复杂度很可能是 或
的。暴力程序的性能瓶颈卡在变量
的循环上，因此考虑优化
的求解，此时就开始了本题的重头戏——斜率优化/凸包优化。
把需要最大化的算式拿出来分析，我们进行化简可以得到：
进行斜率优化时，我们把
看作主元，并且希望让斜率仅和
有关。那我们移项可以得到：
类比直线的斜截式方程 ，发现这个式子可以用数形结合的方式做出来：斜率
，截距 ，纵坐标 ，横坐标 。任务是最大化 dp[i]
的值，考虑到 ，所以只要构造的直线的截距最大，dp[i]
就是最大的。
对于特定斜率的直线，显然是靠上端的直线截距更大，如下图（若绘图有误烦请指出）：
对于不同斜率的点，截距最大的直线所过的点均在一个上凸包上（红线连出）：
同时，当前直线所过的点是第一个斜率比当前直线斜率小的点。“最小值最大”，那不就是二分嘛！别急，这道题可以不用二分，有更简便的方法。
考虑到每次代入的点 ，因为每个士兵的战斗力均为正数，显然它的前缀和不可能出现下降趋势，是单调递增的。又知道
是递增枚举的，所以每次构造的直线的斜率是单调递减的。因此考虑用单调队列维护这个合法点，具体操作如下：
- 当队头点的斜率大于了当前直线的斜率，显然不会再被用到，直接弹出。形式化地，当
时弹队头。
- 当队尾点的斜率小于将要加入的点
的斜率，原先的队尾已经不满足上凸包“斜率单调递减”的要求了，故弹出。也就是说当
时就弹出队尾。
至此，单调队列的队头就是我们所维护的 。把
代入状态转移方程里即可计算出答案了（注意超时的原因是暴力找 ，和状态转移方程本身没关系），由于涉及斜率的计算，要使用浮点数（或者你也可以就使用整型，斜率换成交叉相乘）。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <bits/stdc++.h>
#define N 1000010
using namespace std;
typedef long long ll;
double dp[N];
double x[N], sumX[N];
double a, b, c;
int q[N];
int hh = 0, tt = 0;
double getY(int i) {
return dp[i] + a * sumX[i] * sumX[i] - b * sumX[i];
}
double slope(int x1, int x2) {
return (getY(x1) - getY(x2)) * 1.0 / (sumX[x1] - sumX[x2]) * 1.0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, t;
cin >> t;
while (t--) {
memset(dp, 0, sizeof dp);
memset(x, 0, sizeof x);
memset(sumX, 0, sizeof sumX);
hh = 0, tt = 0;
cin >> n >> a >> b >> c;
for (int i = 1; i <= n; i++) {
cin >> x[i];
sumX[i] = sumX[i - 1] + x[i];
}
q[0] = 0;
for (int i = 1; i <= n; i++) {
while (hh < tt && slope(q[hh + 1], q[hh]) >= 2 * a * sumX[i]) hh++;
int j = q[hh];
double X = sumX[i] - sumX[j];
dp[i] = dp[j] + a * X * X + b * X + c;
while (hh < tt && slope(q[tt], q[tt - 1]) <= slope(i, q[tt])) tt--;
q[++tt] = i;
}
cout << (ll) dp[n] << endl;
}
return 0;
}
|
