斜率优化dp

任务安排1

题目描述

数据范围
$1\le N\le 5000，0\le S\le 50，1\le Ti,Ci\le 100$

令
$sumc[i]$：花费的前缀和

$sunt[i]$：时间的前缀和

如果选择在第$i$个任务处添加一个分组，那么在这里多出来的机器启动时间$S$会对后面的每一个任务都造成影响，导致多出来的花费值是$S\ast (sumc[n]-sumc[i])$，为了不影响后面的dp，所以对后面的任务造成的花费直接在$i$处加上。

定义f[i]表示前i个任务分组的最小花费。

则有 f i = m i n { f j + s u m t i ∗ ( s u m c i − s u m c j ) + S ∗ ( s u m c n − s u m c j )    ∣   0 ≤ j ≤ i − 1   } f_i=min \{ f_j + sumt_i*(sumc_i-sumc_j) + S*(sumc_n-sumc_j) \ \ | \ 0 \le j \le i-1 \ \} fi​=min{fj​+sumti​∗(sumci​−sumcj​)+S∗(sumcn​−sumcj​)  ∣ 0≤j≤i−1 }

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;

int n, s;
long long dp[N], sumt[N], sumc[N];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    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(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < i; j ++) {
            dp[i] = min(dp[i], dp[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
        }
    }
    cout << dp[n];
    
    return 0;
}

任务安排2

题意与任务安排1相同，但是数据范围有变。
数据范围: $1\le N\le 3\times 1e5，1\le Ti,Ci\le 512，0\le S\le 512$

之前的做法是$O(n^2)$，但是本题$n\le 3e5$，于是需要对上面的转移式子进行优化。

这里要用到的就是斜率优化dp。

在求$f_i$时，需要遍历每一个$f_j，(j<i)$，我们可以把与i相关的值看成常量，将与j有关的值看成变量。

更具体的，将$f_j$看成$y$，$sum{c}_j$看成$x$。

    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]));
        }
    }

$f_i=f_j-(sum{t}_i+S)\ast sum{c}_j+sum{t}_i\ast sum{c}_i+S\ast sum{c}_n$

左右移项得到$f_j=(sum{t}_i+S)\ast sum{c}_j+f_i-sum{t}_i\ast sum{c}_i-S\ast sum{c}_n$

可以将其看成直线表达式:$y=kx+b$的形式。其中斜率$k$是一个定值。

这个直线表达式上的点$(x,y)$取值可以是：$(sum{c}_0,f_0),(sum{c}_1,f_1),(sum{c}_2,f_2),...,(sum{c}_{i-1},f_{i-1})$。不同的取值代入上面的式子可以得到不同的$f_i$。我们的目标是使得$f_i$最小，也就是让直线表达式中的截距$b$最小。

根据上图，我们需要维护这些点的凸包的下边界，因为对于某一个直线来说，与它距离最近的点一定是在这些点上。

• 如果该直线的斜率为k，怎么找到与它距离最近的点？

我们将凸包上的相邻两点组成直线的斜率标出来，如上图，可以发现$k_1<k_2<k_3$。

而$k_1<k<k_2$。于是我们只需要找到第一个斜率大于k的位置的点。

• 另外，本题还有一些其他性质，由于这两个特殊的性质，我们可以进行均摊$O(1)$的转移。

1、斜率$k=sum{t}_i+S$,因为$t$和$S$都是大于$0$的，所以我们从$1$到$n$求$f_i$时，其对应询问的直线的斜率是单调递增的。

​ 因此，在查询时，如果队头某些点(斜率小于当前直线斜率)不可能作为答案，那么它在后面时更不可能作为答案，可以直接删除。

2、我们不断新加点$(sum{c}_j,f_j)$时，新加点的横坐标也是单调递增的。因为$c$是大于$0$的。

​ 这意味着我们新加入的点一定不会被删掉。如果新加的点可以和队列末尾的点组成凸包，那么加进去，否则将末尾的点删掉，直到可以和队列中的点组成凸包。

#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define all(x) begin(x),end(x)
#define debug(x) cout<<#x<<": "<<x<<endl;
using namespace std;
using ll = long long;
const int N = 3e5 + 10;

int n, s, q[N];
ll c[N], t[N], f[N];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	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 = -1;
	q[++ tt] = 0;  // (c[0], f[0])
	for (int i = 1; i <= n; i ++) {
		// 求f[i], 对应直线斜率k=t[i]+s
		// hh < tt 确保队列中有>=2个点，若队头点组成的斜率小于当前斜率，出队
		while (hh < tt && (f[q[hh + 1]] - f[q[hh]]) <= (t[i] + s) * (c[q[hh + 1]] - c[q[hh]]))	hh ++;
		int j = q[hh];  // 此时最优转移点就是队头的点
		f[i] = f[j] - (t[i] + s) * c[j] + t[i] * c[i] + s * c[n];
		//将点(c[i], f[i])加入队列，加入前将不符合条件的点出队
		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;
}

CF1715E Long Way Home

题意

数据范围：$1\le n,m\le 1e5，1\le k\le 20，1\le w\le 1e9$。

我们先用$dijstra$求出$dis{t}_i$，表示只走道路从$1$到$i$的最小值。

• 然后考虑只飞一次，能使得$dis{t}_i$如何更新？

另设一个数组$dp$，其中$d{p}_i$表示飞完后从$1$到$i$的最短花费。

对于$dis{t}_i$，我们只需要处理从$1$到$i$最后一次是飞的最短花费。
即其路线是$1\to j\to i$，那么 d p i = m i n { d i s t j + ( i − j ) 2    ∣ 1 ≤ j ≤ n   } dp_i=min\{dist_j + (i-j)^2 \ \ | 1\le j \le n \ \} dpi​=min{distj​+(i−j)2  ∣1≤j≤n }。
然后更新之后我们将所有被更新过的点放入优先队列中在跑一边$dijstra$。
这样就得到了只飞一次的最小花费。
题目要求$k$次，且$k\le 20$，那么我们循环$k$次这个过程即可。

• 还有一个问题是转移方程是$O(n)$的一个转移，求$n$个合起来就是$O(n^2)$，显然需要优化。

d p i = m i n { d i s t j + ( i − j ) 2    ∣ 1 ≤ j ≤ n   } dp_i=min\{dist_j + (i-j)^2 \ \ | 1\le j \le n \ \} dpi​=min{distj​+(i−j)2  ∣1≤j≤n }。
可以写成 $dis{t}_j+j^2=2ij+d{p}_i-i^2$。
这里将其看成$y=kx+b$。

其中$Y_i=dis{t}_i+i^2，X_i=i$。
注意本题也有与任务安排类似的特殊性质：即每个直线的斜率k是单调递增的，新加入的点的横坐标也是单调递增的。
有些题目不满足上面的性质，那么维护时就要使用一些其他的方法。

#include <bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
#define all(x) begin(x),end(x)
#define debug(x) cout<<#x<<": "<<x<<endl;
using namespace std;
using ll = long long;
const int N = 1e5 + 10;

int n, m, k, q[N];
ll dist[N], dp[N];
vector<pair<int, int>> g[N];
bool vis[N];

priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> Q;

void dijkstra() {
	memset(vis, 0, sizeof vis);
	while (Q.size()) {
		auto [d, u] = Q.top();
		Q.pop();
		if (vis[u])	continue;
		vis[u] = true;
		for (auto &[v, w]: g[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				if (!vis[v])	Q.emplace(dist[v], v);
			}
		}
	}
}

inline ll X(ll i) { return i; }
inline ll Y(ll i) { return dp[i] + i * i; }
inline double slope(ll i, ll j) {  // 由于范围太大，交叉相乘判大小会溢出，只能用除法
	return (double)(Y(j) - Y(i)) / (X(j) - X(i));
}


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> n >> m >> k;
	while (m --) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
	Q.emplace(dist[1], 1);
	dijkstra();
	
	for (int _ = 1; _ <= k; _ ++) {
		for (int i = 1; i <= n; i ++)	dp[i] = dist[i];
		// 维护所有点的凸包
		int hh = 0, tt = -1;
		for (int i = 1; i <= n; i ++) {
			while (hh < tt && slope(q[tt - 1], q[tt]) >= slope(q[tt], i))	tt --;
			q[++ tt] = i;
		}
		// 寻找最优转移点更新dist
		for (int i = 1; i <= n; i ++) {
			while (hh < tt && slope(q[hh], q[hh + 1]) <= 2ll * i)	hh ++;
			int j = q[hh];
			if (dist[i] > dp[j] + (ll)(i - j) * (i - j)) {
				dist[i] = dp[j] + (ll)(i - j) * (i - j);
				Q.emplace(dist[i], i);
			}
		}
		dijkstra();
	}
	
	for (int i = 1; i <= n; i ++)	cout << dist[i] << " \n"[i == n];
	
	return 0;
}