题解：P7747 [COCI 2011/2012 #3] TRAKA
j23wuyifan
·
·
题解
Solution
设 f[i] 表示第 i 辆汽车开始加工的时间，t[i] 表示对每个工人完成工作时间做的前缀和，g[i] 表示题目中的 f[i]。
题目中的：根据公司政策，一个工人完成他的工作后，他必须立即将工作交给下一个工人，不得拖延。表明每个工人 j 开始加工第 i 的时间一定大于等于他加工完第 i 辆车的时间。就有：
f[i] + t[j-1] \times g[i] \ge f[i - 1] + t[j] \times g[i - 1]
f[i] \ge f[i - 1] + t[j] \times g[i - 1] - t[j-1] \times g[i]
f[i] = f[i - 1] + \max_{j=1}^{n} (t[j] \times g[i - 1] - t[j-1] \times g[i])
暴力枚举 j，可以获得 40 分。
考虑斜率优化，式子右边提取出 g[i-1] 或 g[i]，得到：
f[i] = f[i - 1] + g[i-1] \times \max_{j=1}^{n} (t[j] - t[j-1] \times \frac{g[i]}{g[i-1]})
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int f[N], t[N], g[N], n, m, q[N];
//f[i] 表示第 i 辆车的最早开始时间
inline int X(int i) {return t[i - 1];}
inline int Y(int i) {return t[i];}
signed main() {
cin >> n >> m;
int r = 0;
for (int i = 1; i <= n; i ++) {
cin >> t[i], t[i] += t[i - 1];
//维护上凸壳(斜率递减)，x = t[i - 1],y = t[i]
while (r > 1 && (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])) > (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])))r --;
q[++ r] = i;
}
for (int i = 1; i <= m; i ++) cin >> g[i];
f[1] = 0;
for (int i = 2; i <= m; i ++) {
//k = g[i] / g[i - 1]
int ll = 1, rr = r, res;
//二分找最值
while (ll <= rr) {
int mid = ll + rr >> 1;
//斜率 <= k
if ((Y(q[mid + 1]) - Y(q[mid])) * g[i - 1] <= (X(q[mid + 1]) - X(q[mid])) * g[i]) {
res = mid;
rr = mid - 1;
} else ll = mid + 1;
}
f[i] = f[i - 1] + g[i - 1] * t[q[res]] - t[q[res] - 1] * g[i];
}
cout << f[m] + t[n] * g[m];
return 0;
}
```