python/TangDou/AcWing/ConvexHullTrick/300_0.cpp

#include <bits/stdc++.h>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 5010;
int t[N], c[N];
int f[N][N];
int n, s;
/**
 5
1
1 3
3 2
4 3
2 3
1 4

 答案：153

 二维数组：
 5000*5000=25000000

 25000000 * 4byte=100000000 byte = 100000 kb =  100 mb >题目要求的64mb ，所以不出意外：
 MLE了！还没有来的及TLE，先MLE了！看来需要一个一维的状态表示方法！
 */
int main() {
    // 任务个数与启动时间
    cin >> n >> s;

    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1]; // t数组自带前缀和
        c[i] += c[i - 1]; // c数组自带前缀和
    }

    /* 1、为什么这样初始化？
      答：看状态转移方程
      f[i][j] = min(f[i][j], f[k][j - 1] + (j * s + t[i]) * (c[i] - c[k]));
      f[i][j]：前i个任务，在j个阶段的场景下，最小的代价值是多少。

      这个k好说，有上面的循环限制了它的范围。
      这个j-1就要小心了，不能小于零吧~，而且，如果等于0是啥意思，也要从现实意义出发进行初始化设置
      j-1=0,也就是说在第0个阶段，第0个阶段就是还没有开始,管你前多少个任务，代价值都应该是0
     */
    memset(f, 0x3f, sizeof f);
    memset(f[0], 0, sizeof f[0]);

    // 2、开始填表
    for (int i = 1; i <= n; i++)                                                      // i个任务
        for (int j = 1; j <= i; j++)                                                  // j个阶段，注意j的上界，一个阶段1个任务是极限，此时i=j
            for (int k = j - 1; k < i; k++)                                           // 最后一个阶段的起点k
                f[i][j] = min(f[i][j], f[k][j - 1] + (s * j + t[i]) * (c[i] - c[k])); // 前缀和 \sum_{a=k+1}^{i}c[a]

    /*
     3、收集答案
     f[n]表示在n个任务,那么划分的分组数量可能是多少呢？是1，2，3，...n,其中1表示全部划归一组,n表示一个任务一组，共n组
    */
    int res = INF;
    for (int i = 1; i <= n; i++) res = min(res, f[n][i]);
    cout << res << endl;
    return 0;
}