题解 P2365 【任务安排】

· · 题解

首先，这是一个DP。

（似乎是个叫分组DP的东西）

显然的状态定义：用 dp_i 表示前 i 个任务都被完成，所需的时间最小值。（因为 f 用过了，只好用 dp 了qwq）

显然的转移方程：

dp_i = \min\limits_{1 \leqslant j \leqslant i}{dp_{j-1} + \sum\limits_{k = j}^i{tim \times f_k}} = \min\limits_{1 \leqslant j \leqslant i}{dp_{j-1} + tim \times \sum\limits_{k = j}^i{f_k}} 后面的 $ \sum\limits_{k = j}^i{f_k} $ 显然可以用前缀和维护。但是变量 $ tim $ 的出现似乎给算法带来了后效性，因为它与之前分过的组数有关。更确切地说， $ tim = \sum\limits_{k = 1}^i{t_k} + num \times S

其中 num 是之前已经分过的组数。同样地， \sum\limits_{k = 1}^i{t_k} 可以用前缀和维护。而对于 num ，如果再开一维 dp 数组维护（枚举），开销将会很大。

如何解决？

注意到每在 j 到 i 之间分一组，那么对于之后所有的 k ，其计算时的 num 都会加上 1 。对于 tim 而言就是加上 S 。抛开转移方程讲，就是 这一组 以及后续所有任务的完成时间都要加上 S 。那么对于每个任务 k ，它所需要的费用会加上 S \times f_k ，后面的所有任务总共就会加上 \sum\limits_{k = j}^n{S \times f_k}

= S \times \sum\limits_{k = j}^n{f_k} 那么为什么不把这些费用提在计算 $ f_i $ 时就计算呢？ 于是我们得出了新的转移方程： $ f_i = \min\limits_{1 \leqslant j \leqslant i}{dp_{j-1} + \sum\limits_{k = 1}^i{t_k} \times \sum\limits_{k = j}^i{f_k}} + \sum\limits_{k = j}^n{f_k} \times S

这时计算当前段代价时， tim 不用再加上机器的启动时间，因为这些时间造成的代价都已经在之前的 i 中计算过了。而这一次启动对后面的任务所产生的额外代价，则是 \sum\limits_{k = j}^n{f_k} \times S 。

注意到方程中所有的 \sum 都是可以用前缀和维护的。

所以这个转移方程就是 O(n) 的。共有 O(n) 个状态。总时间复杂度为 O(n^2) ，空间复杂度为 O(n) ，已经足以通过此题了。

（似乎还有更快的做法？布吉岛还是要%%%大佬们）

Code:

#include<bits/stdc++.h>
using namespace std;
int t[5001],f[5001],st[5001],sf[5001],dp[5001];
int main()
{
    int n,s;
    scanf("%d %d",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&t[i],&f[i]);
        st[i]=st[i-1]+t[i];
        sf[i]=sf[i-1]+f[i];
    }
    memset(dp,0x7f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            dp[i]=min(dp[i],dp[j-1]+st[i]*(sf[i]-sf[j-1])+s*(sf[n]-sf[j-1]));
    printf("%d\n",dp[n]);
    return 0;
}