[AcWing面向模型编程]斜率优化dp

题目1：300. 任务安排1

分析：

直接去想的话，状态转移的时候无法得知上一个状态到底划分了几批，无法计算总的时间。但是如果每次我们计算状态的时候，将当前的一次划分的时间s对后面所有的任务产生的花费计算在内的话，问题就变得很简单了。

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; //typedef __int128 lll; #define print(i) cout << "debug: " << i << endl #define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define mem(a, b) memset(a, b, sizeof(a)) const ll mod = 1e9 + 7; const int maxn = 1e4 + 10; const int inf = 0x3f3f3f3f; int n, s; int t[maxn], c[maxn]; int dp[maxn]; int main() { cin >> n >> s; for(int i = 1; i <= n; i++) cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1]; mem(dp, inf); dp[0] = 0; for(int i = 1; i <= n; i++) for(int j = 0; j < i; j++) dp[i] = min(dp[i], dp[j] + (c[i] - c[j]) * t[i] + s * (c[n] - c[j])); cout << dp[n] << endl; }

斜率优化dp的情景

题目2：300. 任务安排1

分析：

本题是对上一题的优化。通过对等式进行合并同类项（i看成常数，j看成未知量），找到y，k，x。目标是最小化f[i]，于是我们要维护一个下凸包。 注意：一开始队列含有0，用于进行后续转移。

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; //typedef __int128 lll; #define print(i) cout << "debug: " << i << endl #define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define mem(a, b) memset(a, b, sizeof(a)) const ll mod = 1e9 + 7; const int maxn = 1e4 + 10; const int inf = 0x3f3f3f3f; int n, s; ll t[maxn], c[maxn]; ll dp[maxn]; int q[maxn]; ll gety(int i) { return dp[i]; } ll getx(int i) { return c[i]; } int main() { cin >> n >> s; for(int i = 1; i <= n; i++) cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1]; dp[0] = 0; int l = 0, r = 0; q[0] = 0; for(int i = 1; i <= n; i++) { while(l < r && (gety(q[l + 1]) - gety(q[l])) <= (getx(q[l + 1]) - getx(q[l])) * (t[i] + s)) l++; int j = q[l]; dp[i] = dp[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]); while(l < r && (gety(q[r]) - gety(q[r - 1])) * (getx(i) - getx(q[r])) >= (getx(q[r]) - getx(q[r - 1])) * (gety(i) - gety(q[r]))) r--; q[++r] = i; } cout << dp[n] << endl; }

题目3：302. 任务安排3 分析： 这个题斜率不是递增的，改用二分查找。 套上求满足题意的值中的最小值的模板代码。 代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; // #define print(i) cout << "debug: " << i << endl #define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define mem(a, b) memset(a, b, sizeof(a)) const ll mod = 1e9 + 7; const int maxn = 1e6 + 10; const int inf = 0x3f3f3f3f; int n, s; lll t[maxn], c[maxn]; lll dp[maxn]; int q[maxn]; inline lll read(){ lll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } inline void print(lll x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) print(x / 10); putchar(x % 10 + '0'); } lll gety(int i) { return dp[i]; } lll getx(int i) { return c[i]; } int main() { cin >> n >> s; for(int i = 1; i <= n; i++) t[i] = read(), c[i] = read(), t[i] += t[i - 1], c[i] += c[i - 1]; dp[0] = 0; int l = 0, r = 0; q[0] = 0; for(int i = 1; i <= n; i++) { int down = l, up = r; while(down <= up) { int mid = down + up >> 1; if(gety(q[mid + 1]) - gety(q[mid]) > (t[i] + s) * (getx(q[mid + 1]) - getx(q[mid]))) up = mid - 1; else down = mid + 1; } int j = q[down];//因为是求第一个斜率>当前直线的斜率的点，所以用down访问 dp[i] = dp[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]); while(l < r && (gety(q[r]) - gety(q[r - 1])) * (getx(i) - getx(q[r])) >= (getx(q[r]) - getx(q[r - 1])) * (gety(i) - gety(q[r]))) r--; q[++r] = i; } print(dp[n]); }