斜率优化

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 小助理，如未能正确解答您的问题，请继续追问。