理解题意
将线性序列任务分为若干批, 每批均需要启动时间$s$, 每批任务的花费为
该批任务的结束时刻 $\times$ 该批任务所需费用之和.
本题一个难点是当在$i$任务之后划分新一批任务时, 该批的启动时间$s$会影响$i + 1\sim n$后续
所有任务的结束时间. 这里使用了花费提前计算的思想 — 将$s$对后续的影响放在$i + 1$批任务
内, 而不需要依次考虑后续所有批次任务.
$DP$分析
状态表示
线性序列, 且没有其他条件限制, 状态可直接用一维表示.
-
集合: $f(i)$ — 将前$i$个任务分批次的所有方案.
-
属性:
Min
花费
状态计算
以上一批任务的最后一个任务作为划分依据. 设上一批最后一个任务为$j$, 则以$i$作为最后
一批任务范围是$j + 1\sim i, 0\le j\le i - 1$. 此时集合划分为两部分:
-
不确定部分: 前$j$个任务的划分方案, 对应状态$f(j)$.
-
确定部分: $j + 1\sim i$, 假设任务花费时间与费用的前缀和分别为$sumt$与$sumc$,
则确定部分所需花费为任务花费$sumt_i\times (sumc_i-sumc_j)$与启动时间带来的
花费$s\times (sumc_n-sumc_j)$之和.
综上, $f(i) = max\lbrace f(j) + sumt_i\times (sumc_i-sumc_j) + s\times (sumc_n-sumc_j)\rbrace, 0\le j\le i$.
代码实现 $O(n^2)$
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5010;
int n, s;
ll sumt[N], sumc[N];
ll f[N];
int main()
{
cin >> n >> s;
for ( int i = 1; i <= n; i ++ )
{
cin >> sumt[i] >> sumc[i];
sumt[i] += sumt[i - 1];
sumc[i] += sumc[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] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
cout << f[n] << endl;
return 0;
}