线性dp

普通版 N ⇐ 5000

300. 任务安排1 - AcWing题库 整理动态规划转移方程, 然后抽象, 挖掘有什么数学性质。 有 $N$ 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。

机器会把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。

从时刻 $0$ 开始，任务被分批加工，执行第 $i$ 个任务所需的时间是 $T_i$。

另外，在每批任务开始前，机器需要 $S$ 的启动时间，故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行包含整数 $N$。

第二行包含整数 $S$。

接下来 $N$ 行每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间 $T_i$ 及其费用系数 $C_i$。

输出格式

输出一个整数，表示最小总费用。

数据范围

$1\le N\le 5000$,
$0\le S\le 50$,
$1\le T_i,C_i\le 100$

输入样例：

5
1
1 3
3 2
4 3
2 3
1 4

输出样例：

153

思路

根据题目要求可得有一种划分方式得到的代价为： 每个划分的代价可变的部分取决于该区间结束时的时间time, 同一段任务可能因为先后顺序不同而代价不同。

对于启动时间S, 在任意时刻启动时, 都会对后面所有的任务段造成影响, 让他们的 time + S, 可以直接提前算掉当前任务所带来的花费, 即：$S\ast (C_{j+1}+C_{j+2}+C_{j+3}...+C_n)$

把花费重新整合一下, 这个思想在很多数学定理的证明中会使用。

序列DP可以先用一维表示。 状态表示：f[i]前i个任务处理完的所有方案的集合, 值为最小代价 状态计算： 找f[i]这个集合所有方案的差异性, 显然这里可以从最后一个区间的长度来划分：

• 当长度为[1,i]时, 划分了所有任务, 从f[0]转移过来
• 当长度为[2,i]时, 划分了i-1个任务, 从f[1]转移过来
• 最后是当长度为[i,i], 即只有i一个任务时, 从f[i-1]转移过来 进一步考虑 故得出了转移方程f[i] = f[j] + sumT[i]*(sumC[i]-sumC[j])+S*(sumC[n]-sumC[j]) 初始时总费用为0。 注意题目中最大整数可能为$(100\ast 5000{)}^2+50\ast 5000=2.5e11$, 故需要开long long。

这种方式计算的话总状态数量为$N$, 状态计算为$N$, 总时间复杂度为$O(N^2)$ 根据题目范围$N<=5000$, 是可以过的。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5e3 + 10;
long long t[N], c[N];
long long f[N];
int n,s;
 
 
int main()
{
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[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] + t[i]*(c[i] - c[j]) + s*(c[n] - c[j]));
        }
    }
    cout << f[n] << endl;
    return 0;
}

当N为3e5时

$O(N^2)$的算法无法通过, 需要进行优化。 DP问题正确性和优化是分开思考的, 这里就只需要考虑这个式子怎么化简即可。

$f[i]=f[j]+sumT[i]\ast (sumC[i]-sumC[j])+S\ast (sumC[n]-sumC[j])$ 当状态计算到i时, 我们需要枚举的只有j, 也就是说只有j是变量。 做类似于单调队列优化的变量分离： 方程错了, 后面的$S\ast sumC[n]$ 应该是减去。 因为题目中sumT,S都为正数且有限, 故该直线只会在第一象限波动, 画出坐标系： 所有x,y的取值为$\{(f[0],sumC[0]),(f[1],sumC[1]),...,(f[n],sumC[n])\}$, 而我们的目标是求出f[i]的最小值, 且此时k是常数, 不同的x,y取值会导致不同的截距, 也会导致f[i]的值不同。

显然对于所有可能的x,y点, 只需要找到最底下的就可以找到最小的f[i]： 此时截距最小, 而sumT[i]*sumC[i]+S*sumC[n]是常量, 故f[i]为最小。 同理对于所有f[i]对应的斜率k, 都能找到一个点, 使其截距最小。

但如果仅仅是这样, 还需要对于每个i枚举所有的j, 并没有优化。观察一下可以发现, 不是所有的点都会被当做最小的那个点。枚举所有可能的斜率直线可以发现对答案有贡献的点只有偏右下部分的点： 即标红的点。

而这些标红的点对于任何斜率的直线, 当有一点在直线上时, 其他点必定在直线的一侧。这就符合了凸包的定义。也是为什么叫做凸包优化。

但只是枚举凸包下边界所有点也不行, 最坏情况还是$O(n)$, 所以我们必须以更快的方式找到每个直线对应的最小点。 求出凸包下边界相邻点的斜率, 显然可以发现, 当k1<k<=k2时, 中间的点最优。 即第一个斜率大于k的点是该直线的最小点。 而凸包中的点斜率随着x增大是单调递增的, 那么要找到这个>k的第一个点, 最传统的方式是二分 $O(logN)$ 。 但如果有其他性质的话可以更加优化：

• 题目中T都为整数, 故sumT[i]*S即斜率k是单调递增的
• i从低到高枚举时, k单调递增, 即每个新直线不会用到之前用过的最小点 因此, 当用一个队列维护凸包下边界点时： $\frac{f_2-f_1}{sum{C}_2-sum{C}_1}<=sum{T}_i+S$ , 查询的时候可以把队头小于当前斜率的点全部删掉。 $\frac{f_{tt}-f_{tt-1}}{sum{C}_{tt}-sum{C}_{tt-1}}>=\frac{f_i-f_{tt}}{sum{C}_i-sum{C}_{tt}}$ 插入的时候把队尾不在凸包上的点全删掉。 这个过程其实就是Graham’s Scan算法中下边界的求法。原算法开始时有一步是要对所有点关于x从小到大排序然后枚举, 这里则因为sumC[i]是递增的故省去。

代码

#include<iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
LL c[N], t[N];
LL f[N];
int q[N];
int n,s;
 
 
int main()
{
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
    
    int hh = 0, tt = 0;
    q[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        while(hh < tt && f[q[hh + 1]] - f[q[hh]] <= (c[q[hh + 1]] - c[q[hh]]) * (t[i] + s)) hh++;
        int j = q[hh];
        f[i] = f[j] - c[j]*(t[i] + s) + t[i]*c[i] + s*c[n];
        while(hh < tt && (f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]])) tt--;
        q[++tt] = i;
    }
    cout << f[n] << endl;
    return 0;
    
}

当T可以为负数时

$1\le N\le 3\ast 10^5$,
$0\le S,C_i\le 512$,
$-512\le T_i\le 512$

那么 sumT 将不一定为整的, 也就是说斜率 $k=sumT[i]\ast s$ 不一定单调递增。但新加的点还是单调递增的。

在查询的时候就不能把小于当前斜率的点全删掉, 因为可能后续斜率为负数会用到, 故用二分来查询。 而在插入的时候, 和之前一样把队尾不在凸包上的点全部删掉即可。

注意最后的 long long 乘法会溢出, 需要加 double。

#include <iostream>
using namespace std;
const int N = 3e5 + 10;
 
typedef long long LL;
LL f[N];
LL c[N], t[N];
int q[N];
int n, s;
 
int main()
{
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i] >> c[i];
        t[i] += t[i - 1];
        c[i] += c[i - 1];
    }
 
    int hh = 0, tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = hh - 1, r = tt + 1;
        while (l != r - 1)
        {
            int mid = l + r >> 1;
            if (f[q[mid + 1]] - f[q[mid]] >= (t[i] + s) * (c[q[mid + 1]] - c[q[mid]]))
                r = mid;
            else
                l = mid;
        }
        int j = q[r];
        f[i] = f[j] - c[j] * (t[i] + s) + t[i] * c[i] + s * c[n];
        while (hh < tt && (double)(f[q[tt]] - f[q[tt - 1]]) * (c[i] - c[q[tt]]) >= (double)(f[i] - f[q[tt]]) * (c[q[tt]] - c[q[tt - 1]]))
            tt--;
        q[++tt] = i;
    }
    cout << f[n] << endl;
    return 0;
}