首先你要把题目彻底读懂。
若设 $f[i][j]$ 表示前 $i$ 个任务,第 $i$ 个任务包括在第 $j$ 批次的最小总费用,则:
$$
f[i][j]=\min\limits_{k=0}^{i-1}\left(f[k][j-1]+\left(jS+\sum\limits_{a=1}^{i}T_a\right)\sum_{b=k+1}^{i}C_b\right)
$$
其中 $jS$ 为前面所有批次的启动时间之和,$\sum T_i$ 为完成任务总耗时,加在一起为该批次完成时刻,$\sum C_i$ 为费用系数区间和。
但这样的时间复杂度为 $O(n^3)$,其中 $i$ 为 dp 主阶段,$k$ 为决策变量,都不可省略;$j$ 只是用于确定 $jS$ 的变量,考虑优化掉这一维:
原本每一组的结束时间中的 $S$ 都是乘上批次数 $j$ 单独计算的,我们考虑提前计算它,即当新开了一个批次,就提前把这个批次给后面造成的 $S$ 的贡献累加好,后面就不用处理了:原本的 $S$ 只对当前批次区间 $[l,r]$ 起作用,之后会重新计算,但现在它会对 $[l,n]$ 起作用,所以要让它乘上 $\sum\limits_{b=k+1}^{n}C_b$,这样以后就不用管了,即新转移方程为:
$$
f[i]=\min\limits_{k=0}^{i-1}\left(f[k]+S\sum\limits_{b=k+1}^{n}C_b+\sum\limits_{a=1}^{i}T_a\sum_{b=k+1}^{i}C_b \right)
$$
其中,$S\sum C_b$ 包括当前贡献和提前计算的后面的贡献,$\sum T_a\sum C_b$ 为当前贡献;这样,时间复杂度就降到了 $O(n^2)$。
这种优化方式比较经典,叫费用提前计算优化。
注意:这样算出来只有 $f[n]$ 是真实值,前面的值都不仅仅代表了自己,还包括了为后面提前计算的启动时间。
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
const int N = 5e3 + 10;
int n, s;
int t[N], c[N];
int f[N];
inline void speedup()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
signed main()
{
speedup();
cin >> n >> s;
for (int i = 1; i <= n; i++)
cin >> t[i] >> c[i];
for (int i = 1; i <= n; i++)
t[i] += t[i - 1], c[i] += c[i - 1];
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] + s * (c[n] - c[j]) + t[i] * (c[i] - c[j]));
cout << f[n] << endl;
return 0;
}