acwing算法提高之动态规划--斜率优化DP

1 专题说明

本专题用来记录使用斜率优化的DP问题。

2 训练

题目1：300任务安排1

C++代码如下，

#include <iostream>
#include <vector>using namespace std;int main() {int n, s;cin >> n >> s;vector<int> sumc(n + 10, 0), sumt(n + 10, 0);vector<long long> f(n + 10, 0);for (int i = 1; i <= n; ++i) {int t, c;cin >> t >> c;sumt[i] = sumt[i-1] + t;sumc[i] = sumc[i-1] + c;}//状态定义f[i]:将前i个任务处理完的所有方案的集合，属性为代价最小。//状态初始化for (int i = 0; i < f.size(); ++i) {f[i] = 0x3f3f3f3f3f3f3f3f; //long long是8个字节}f[0] = 0;//状态转移for (int i = 1; i <= n; ++i) {for (int j = 0; j < i; ++j) {f[i] = min(f[i], f[j] + (long long)sumt[i] * (sumc[i] - sumc[j]) + (long long)s * (sumc[n] - sumc[j]));}}//最终答案cout << f[n] << endl;return 0;
}

题目2：