洛谷 P3620 [APIO/CTSC 2007]数据备份(wqs二分优化 dp)
程序员文章站
2024-02-15 21:48:04
...
最优解肯定是选择了 k 对相邻的办公楼,考虑直接 dp:dp[i][j] 表示前 i 栋楼 选了 j 对的最小花费
,转移方程:dp[i][j] = min(dp[i - 1][j],dp[i - 1][j - 1] + a[i] - a[j])
复杂度为 。考虑优化:若不限制选几对, 在二维平面上肯定是一个下凸函数,二分一个权值 ,使得每个点的答案要减去 ,即答案 = ,从线性规划的角度考虑,这相当于二分一个斜率 ,要让这条直线在这个凸包上切某个点截距最小,由于凸包斜率具有单调性,因此可以二分 。
也可以更直接的理解:若没有限制,最小答案肯定是一条电缆也不用。为每对电缆扣去一个权值 ,然后在不考虑限制的情况下进行 dp 求解, 越大,则最优解使用的电缆越多,否则最优解使用的电缆越少,具有单调性。
二分 ,找到最优时,电缆数 = k的答案。有可能二分不到这个电缆数 = 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;
}