为了理解斜率DP,便写下了这一篇题解(向下看)
包括入队,出队的简单分析(因为其中涉及到决策单调性,但我却还不会,QwQ)
题目描述
有 N 个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。
机器会把这 N 个任务分成若干批,每一批包含连续的若干个任务。
从时刻0开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。
另外,在每批任务开始前,机器需要 S 的启动时间,故执行一批任务所需的时间是启动时间 S 加上每个任务所需时间之和。
一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。
也就是说,同一批任务将在同一时刻完成。
每个任务的费用是它的完成时刻乘以一个费用系数 Ci。
请为机器规划一个分组方案,使得总费用最小。
输入样例
5
1
1 3
3 2
4 3
2 3
1 4
输出样例
153
分析
众所周知,它的普通DP方程,不知道的可以去看看我的另一篇题解
那怎么转移呢?其实可以证明一下:
证明:
假设j1,j2,是f[i]的两个决策转移点,根据方程f[j]=(sumT[i]+s)∗sumF[j]−sumT[i]∗sumF[i]−S∗sumF[n]f[i],
再假设j2优于j1(0<j1<j2<i),那么由j1转移过来的f[i]可以表示为:
f1[i]=f[j1]+sumT[i]*sumF[i]+s*sumF[n]-sumF[j1]*(sumT[i]+s);
j2同理:
f2[i]=f[j2]+sumT[i]*sumF[i]+s*sumF[n]-sumF[j2]*(sumT[i]+s);
刚才说了,j2优于j1,所以f1[i]>=f2[i],移一下项,就变成:
f[j1]-f[j2]>=(sumT[i]+s)*(sumF[j1]-sumF[j2])
由此可见,当出现一个j2使(sumT[i]+s)>=(f[j1]-f[j2])/(sumF[j1]-sumF[j2])时,j2
就是最优决策点。
然后可以手模一下(只有动手才能真正理解),可以发现入队时,假设队尾有两个点j1,j2,加上我们当前的i
点,共三个点,画个图理解一下
出队操作来了。设 k0=sumT[i]+s,于是这里可以分三种情况来讨论:
(1). k0<k2<k1。可知:j1 优于 j2 优于 i 。
(2). k2⩽k0<k1。可知:j1 和 i 均优于 j2。
(3). k2<k1⩽k0。可知:i 优于 j2 优于 j1 。
可以发现,对于这三种情况,j2 始终不是最优解,于是我们可以将 j2 从候选决策点中踢出去(删除)
只留下 j1 和 i。
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=3e5+10;
ll n,s;
ll t[N],c[N],f[N],q[N];
int main()
{
scanf("%lld%lld",&n,&s);
for (int i=1;i<=n;i++)
{
scanf("%lld%lld",&t[i],&c[i]);
t[i]+=t[i-1];
c[i]+=c[i-1];
}
int l=0,r=0;
for (int i=1;i<=n;i++)
{
while(l<r&&(f[q[l+1]]-f[q[l]])<=(t[i]+s)*(c[q[l+1]]-c[q[l]])) l++;
int j=q[l];
f[i]=f[j]+t[i]*c[i]+s*c[n]-c[j]*(t[i]+s);
while(l<r&&(f[q[r]]-f[q[r-1]])*(c[i]-c[q[r-1]])>=(f[i]-f[q[r-1]])*(c[q[r]]-c[q[r-1]])) r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
/*
斜率严格单调递增
*/
/*
斜率严格单调递增,新加的点的横坐标也单调递增
在查询的时候,可以将对头小于当前斜率的点全部删掉
在插入的时候,把队尾上不在当前凸包上的点全部删掉
新加的点
*/
阅读量上千通知
我知道这些,主要是如何判断他是不是凸包和删点的判断条件,再写写吧(懂我意思吧?)
懂