斜率优化
自学一下斜率优化，有一定的理解难度，我理了好久思路P2356 任务安排
// 易推出 dp 式： dp = dp + (sumc - sumc) * sumt + s * (sumc - sumc)
// dp = (s + sumt) * sumc + dp - sumc * sumt - s * sumc
// 转化为一次函数形式 y = k * x + b, y 为 dp, k 为(s + sumt), x 为 sumc,其余为 b
// 那么题意转化为 ---> 求 b 的最小值---> 求直线 y 的最小截距
// 对于所有已知点(sumc, dp), y 的 k 固定, y 的最小截距就是直线 y 向上平移第一个碰到的点产生的截距
// 因此维护一个下凸包即可， 即维护 (dp - dp) / (sumc - sumc) >= k 这么一个不等式，由于其的单调性易联想到单调队列
// 由于 t 可以为负数，因此 k 不一定单调递增，但是我们维护的 (dp - dp) / (sumc - sumc) 具有单调性，因此二分跳跃至正确决策点即可
// Created on 2025/8/10 20:37.
#include <bits/stdc++.h>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define reps(i, j, k) for(int i = j; i >= k; i--)
using namespace std;
const int _ = 3e5 + 7;
int n, s, c, t, f, st, l = 0, r = 0;
int x(int a, int b){
return c - c];
}
int y(int a, int b){
return f - f];
}
int get_pos(int i){
int k1 = l, k3 = r, k = t + s;
while (k1 < k3){
int k2 = (k1 + k3) >> 1;
if (y(k2, st) >= x(k2, st) * k) k3 = k2;
else k1 = k2 + 1;
}
return k1;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> s;
rep(i, 1, n){
cin >> t >> c;
t += t, c += c;
}
rep(i, 1, n){
int pos = st;
f = f + (c - c) * t + s * (c - c);
while (l < r && y(r - 1, st) * x(r, i) >= y(r, i) * x(r - 1, st)) r--;
st[++r] = i;
}
cout << f;
return 0;
}
小小记录一下做的紫题，属于是很大进步了， 个人感觉这题从代码角度比 严格次小生成树 简单很多， 但是思想上难不少，考场还是喜欢 严格次小生成树 这类题目一点{:10_335:} 根据你的描述，你正在学习斜率优化，并尝试解决任务安排问题（P5785）。你的推导思路正确，但代码存在一些问题。以下是修正后的简洁解答：
### 斜率优化核心思路
1. **状态转移方程**：
`dp = min{ dp + sumT*(sumC-sumC) + s*(sumC-sumC) }`
其中 `sumT = Σt`, `sumC = Σc`。
2. **斜率优化转换**：
- 将方程变形为：`dp = (sumT + s) * sumC + (dp - sumT*sumC - s*sumC)`
- 令 `y = dp`, `x = sumC`, `k_i = sumT + s`
- 目标：找到点 `(x, y)` 使截距最小（即 `dp` 最小）
3. **维护下凸包**：
- 用单调队列维护候选点集，保证相邻点斜率递增（下凸包性质）。
- 由于 `k_i` 不单调（`t_i` 可能为负），需在凸包上二分查找第一个斜率 `≥k_i` 的线段左端点。
### 修正代码（附注释）
#include <iostream>
#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
using namespace std;
const int N = 3e5 + 10;
int n, s;
int sumT, sumC, dp, q;
// 斜率比较：判断 (q,q) 与 (q,i) 的斜率大小（避免浮点）
bool check(int a, int b, int c) {
int x1 = sumC - sumC, y1 = dp - dp;
int x2 = sumC - sumC, y2 = dp - dp;
return y1 * x2 >= y2 * x1; // 若成立，则删除队尾b点
}
signed main() {
cin >> n >> s;
rep(i, 1, n) {
int t, c;
cin >> t >> c;
sumT = sumT + t;
sumC = sumC + c;
}
int l = 0, r = 0; // 队列初始化（q=0）
q = 0;
rep(i, 1, n) {
int k = sumT + s; // 当前斜率k_i
// 二分查找最优决策点
int L = l, R = r;
while (L < R) {
int mid = (L + R) >> 1;
// 比较 mid 与 mid+1 的斜率
if (dp] - dp] >= k * (sumC] - sumC]))
R = mid;
else
L = mid + 1;
}
int j = q; // 最优决策点j
// 更新dp
dp = dp + sumT * (sumC - sumC) + s * (sumC - sumC);
// 维护下凸包（删除队尾不满足凸性的点）
while (l < r && check(q, q, i)) r--;
q[++r] = i; // 将i加入队尾
}
cout << dp << endl;
return 0;
}
### 关键点说明
1. **凸包维护**：
- 队列 `q` 存储决策下标，保证相邻点斜率递增（下凸包）。
- 插入新点 `i` 时，若队尾两点 `(a,b)` 与 `(b,i)` 的斜率不满足凸性（即 `check()` 返回 `true`），则删除 `b`。
2. **二分查找**：
- 在队列中二分找到第一个满足 `(dp-dp)/(sumC-sumC) >= k_i` 的 `j`，此时 `j` 是最优决策点。
3. **复杂度**：`O(n log n)`，适用于 `n ≤ 3e5`。
> 提示：若 `t_i ≥ 0`（`k_i` 单调递增），可直接用单调队列将复杂度降至 `O(n)`。本题因 `t_i` 可能为负，故需二分。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 厉害
页:
[1]