欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P3620 [APIO/CTSC 2007]数据备份(wqs二分优化 dp)

程序员文章站 2024-02-15 21:48:04
...

洛谷 P3620 [APIO/CTSC 2007]数据备份(wqs二分优化 dp)


最优解肯定是选择了 k 对相邻的办公楼,考虑直接 dp:dp[i][j] 表示前 i 栋楼 选了 j 对的最小花费,转移方程:dp[i][j] = min(dp[i - 1][j],dp[i - 1][j - 1] + a[i] - a[j])

复杂度为 O(n2)O(n^2)。考虑优化:若不限制选几对, i,dp[n][i]i,dp[n][i] 在二维平面上肯定是一个下凸函数,二分一个权值 slopeslope,使得每个点的答案要减去 slopeislope * i,即答案 = dp[n][i]slopeidp[n][i] - slope * i,从线性规划的角度考虑,这相当于二分一个斜率 slopeslope,要让这条直线在这个凸包上切某个点截距最小,由于凸包斜率具有单调性,因此可以二分 slopeslope

也可以更直接的理解:若没有限制,最小答案肯定是一条电缆也不用。为每对电缆扣去一个权值 slopeslope,然后在不考虑限制的情况下进行 dp 求解,slopeslope 越大,则最优解使用的电缆越多,否则最优解使用的电缆越少,具有单调性。

二分 slopeslope,找到最优时,电缆数 = k的答案。有可能二分不到这个电缆数 = k 的情况,考虑转移时,每个状态取得最优的情况下尽可能的多使用电缆。二分时找到第一个满足 使用电缆数 k\geq k 的解。


代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
const ll inf = 1e14;
int n,k,a[maxn];
ll dp[maxn],tp[maxn],sum;
ll solve(ll x) {
	tp[0] = dp[0] = 0;
	for (int i = 1; i <= n; i++) dp[i] = sum, tp[i] = 0;;
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1]; tp[i] = tp[i - 1];
		if (dp[i - 2] + a[i] - a[i - 1] + x < dp[i]) {
			dp[i] = dp[i - 2] + x + a[i] - a[i - 1];
			tp[i] = tp[i - 2] + 1;
		} else if (dp[i - 2] + x + a[i] - a[i - 1] == dp[i]) {
			if (tp[i - 2] + 1 > tp[i])
				tp[i] = tp[i - 2] + 1;
		}
	}
	return tp[n];
}
int main() {
	scanf("%d%d",&n,&k);
	for (int i = 1; i <= n; i++)
		scanf("%d",&a[i]), sum += a[i];
	ll l = -sum, r = 0;
	while (l < r) {
		ll mid = l + r >> 1;
		if (solve(mid) < k) r = mid;
		else l = mid + 1;
	}
	solve(l - 1);
	printf("%lld\n",dp[n] - 1ll * k * (l - 1));
	return 0;
}