斜率优化DP

引入 一个线性DP题

300. 任务安排1 - AcWing题库

这题n只有5000的数据，n^2可做。

f[i]表示取前i个任务，且第j个任务的最后一个正好是i。

公式：
$$

\begin{align}
f_i &= \min\bigg({
f_j + S \times \sum_{k=j+1}^n c_k + \sum_{k=1}^i t_k \times \sum_{k=j+1}^i c_k
}\bigg) \
前缀和优化：
f_i &= \min\bigg(f_j + S \times (sc_n - sc_j) + st_i \times (sc_i - sc_j)\bigg)
\end{align}
$$
状态转移方程

f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));

本题仅作为题意的说明及公式的推引。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
#define int long long
const int maxn = 5010;

int f[maxn], q[maxn], sumt[maxn], sumc[maxn];
int n, s;

signed main () {
    cin >> n >> s;
    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;
    }
    
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j < i; j ++ ) {
            f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
        }
    }
    cout << f[n] << endl;
}