斜率优化

学习编程中的Ben

自学一下斜率优化，有一定的理解难度，我理了好久思路
P2356 任务安排

1. // 易推出 dp 式： dp[i] = dp[j] + (sumc[i] - sumc[j]) * sumt[i] + s * (sumc[n] - sumc[j])
   
2. // dp[j] = (s + sumt[i]) * sumc[j] + dp[i] - sumc[i] * sumt[i] - s * sumc[n]
   
3. // 转化为一次函数形式 y = k * x + b, y 为 dp[j], k 为(s + sumt[i]), x 为 sumc[i],  其余为 b
   
4. // 那么题意转化为 ---> 求 b 的最小值  --->   求直线 y 的最小截距
   
5. // 对于所有已知点(sumc[j], dp[j]), y 的 k 固定, y 的最小截距就是直线 y 向上平移第一个碰到的点产生的截距
   
6. // 因此维护一个下凸包即可， 即维护 (dp[i] - dp[j]) / (sumc[i] - sumc[j]) >= k 这么一个不等式，由于其的单调性易联想到单调队列
   
7. // 由于 t 可以为负数，因此 k 不一定单调递增，但是我们维护的 (dp[i] - dp[j]) / (sumc[i] - sumc[j]) 具有单调性，因此二分跳跃至正确决策点即可
   
8. // Created on 2025/8/10 20:37.
   
9. #include <bits/stdc++.h>
   
10. #define int long long
    
11. #define rep(i, j, k) for(int i = j; i <= k; i++)
    
12. #define reps(i, j, k) for(int i = j; i >= k; i--)
    
13. using namespace std;
    
14. 
    
15. const int _ = 3e5 + 7;
    
16. int n, s, c[_], t[_], f[_], st[_], l = 0, r = 0;
    
17. 
    
18. int x(int a, int b){
    
19.     return c[b] - c[st[a]];
    
20. }
    
21. 
    
22. int y(int a, int b){
    
23.     return f[b] - f[st[a]];
    
24. }
    
25. 
    
26. int get_pos(int i){
    
27.     int k1 = l, k3 = r, k = t[i] + s;
    
28.     while (k1 < k3){
    
29.         int k2 = (k1 + k3) >> 1;
    
30.         if (y(k2, st[k2 + 1]) >= x(k2, st[k2 + 1]) * k) k3 = k2;
    
31.         else k1 = k2 + 1;
    
32.     }
    
33.     return k1;
    
34. }
    
35. 
    
36. signed main() {
    
37.     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    
38. 
    
39.     cin >> n >> s;
    
40.     rep(i, 1, n){
    
41.         cin >> t[i] >> c[i];
    
42.         t[i] += t[i - 1], c[i] += c[i - 1];
    
43.     }
    
44. 
    
45.     rep(i, 1, n){
    
46.         int pos = st[get_pos(i)];
    
47.         f[i] = f[pos] + (c[i] - c[pos]) * t[i] + s * (c[n] - c[pos]);
    
48.         while (l < r && y(r - 1, st[r]) * x(r, i) >= y(r, i) * x(r - 1, st[r])) r--;
    
49.         st[++r] = i;
    
50.     }
    
51. 
    
52.     cout << f[n];
    
53. 
    
54.     return 0;
    
55. }
    

复制代码

小小记录一下做的紫题，属于是很大进步了， 个人感觉这题从代码角度比 严格次小生成树 简单很多， 但是思想上难不少，考场还是喜欢 严格次小生成树 这类题目一点

FishC

根据你的描述，你正在学习斜率优化，并尝试解决任务安排问题（P5785）。你的推导思路正确，但代码存在一些问题。以下是修正后的简洁解答：

### 斜率优化核心思路
1. **状态转移方程**：  
   `dp[i] = min{ dp[j] + sumT[i]*(sumC[i]-sumC[j]) + s*(sumC[n]-sumC[j]) }`  
   其中 `sumT[i] = Σt[1..i]`, `sumC[i] = Σc[1..i]`。

2. **斜率优化转换**：  
   - 将方程变形为：`dp[j] = (sumT[i] + s) * sumC[j] + (dp[i] - sumT[i]*sumC[i] - s*sumC[n])`  
   - 令 `y = dp[j]`, `x = sumC[j]`, `k_i = sumT[i] + s`  
   - 目标：找到点 `(x, y)` 使截距最小（即 `dp[i]` 最小）

3. **维护下凸包**：  
   - 用单调队列维护候选点集，保证相邻点斜率递增（下凸包性质）。  
   - 由于 `k_i` 不单调（`t_i` 可能为负），需在凸包上二分查找第一个斜率 `≥k_i` 的线段左端点。

### 修正代码（附注释）

1. #include <iostream>
   
2. #define int long long
   
3. #define rep(i, a, b) for (int i = a; i <= b; i++)
   
4. using namespace std;
   
5. 
   
6. const int N = 3e5 + 10;
   
7. int n, s;
   
8. int sumT[N], sumC[N], dp[N], q[N];
   
9. 
   
10. // 斜率比较：判断 (q[r-1],q[r]) 与 (q[r],i) 的斜率大小（避免浮点）
    
11. bool check(int a, int b, int c) {
    
12.     int x1 = sumC[b] - sumC[a], y1 = dp[b] - dp[a];
    
13.     int x2 = sumC[c] - sumC[b], y2 = dp[c] - dp[b];
    
14.     return y1 * x2 >= y2 * x1; // 若成立，则删除队尾b点
    
15. }
    
16. 
    
17. signed main() {
    
18.     cin >> n >> s;
    
19.     rep(i, 1, n) {
    
20.         int t, c;
    
21.         cin >> t >> c;
    
22.         sumT[i] = sumT[i - 1] + t;
    
23.         sumC[i] = sumC[i - 1] + c;
    
24.     }
    
25. 
    
26.     int l = 0, r = 0; // 队列初始化（q[0]=0）
    
27.     q[0] = 0;
    
28. 
    
29.     rep(i, 1, n) {
    
30.         int k = sumT[i] + s; // 当前斜率k_i
    
31.         
    
32.         // 二分查找最优决策点
    
33.         int L = l, R = r;
    
34.         while (L < R) {
    
35.             int mid = (L + R) >> 1;
    
36.             // 比较 mid 与 mid+1 的斜率
    
37.             if (dp[q[mid + 1]] - dp[q[mid]] >= k * (sumC[q[mid + 1]] - sumC[q[mid]]))
    
38.                 R = mid;
    
39.             else
    
40.                 L = mid + 1;
    
41.         }
    
42.         int j = q[L]; // 最优决策点j
    
43.         
    
44.         // 更新dp[i]
    
45.         dp[i] = dp[j] + sumT[i] * (sumC[i] - sumC[j]) + s * (sumC[n] - sumC[j]);
    
46.         
    
47.         // 维护下凸包（删除队尾不满足凸性的点）
    
48.         while (l < r && check(q[r - 1], q[r], i)) r--;
    
49.         q[++r] = i; // 将i加入队尾
    
50.     }
    
51.     cout << dp[n] << endl;
    
52.     return 0;
    
53. }

复制代码

### 关键点说明
1. **凸包维护**：  
   - 队列 `q` 存储决策下标，保证相邻点斜率递增（下凸包）。  
   - 插入新点 `i` 时，若队尾两点 `(a,b)` 与 `(b,i)` 的斜率不满足凸性（即 `check()` 返回 `true`），则删除 `b`。

2. **二分查找**：  
   - 在队列中二分找到第一个满足 `(dp[j+1]-dp[j])/(sumC[j+1]-sumC[j]) >= k_i` 的 `j`，此时 `j` 是最优决策点。

3. **复杂度**：`O(n log n)`，适用于 `n ≤ 3e5`。

> 提示：若 `t_i ≥ 0`（`k_i` 单调递增），可直接用单调队列将复杂度降至 `O(n)`。本题因 `t_i` 可能为负，故需二分。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

某一个“天”

厉害