贪心反悔,首先读完题我们可以发现一个特别基础得贪心,就是电缆只能在相邻点之间连接,不然就是浪费了电缆长度还浪费了点,所以就把体验转化成了,n - 1个点,点权是相邻两个点的差(绝对值),我们在这些点之中选择K个点,并且要求相邻的两个点不可以都选上。
我们想了想,简单的贪心就是用一个堆,每次只选最小的,可是非常容易hack掉,当前最优并不一定是全局最优,就比如我选择了当前最优解 i, i - 1,i + 1这些点无法选择,在选择就是 除了 i,i - 1,i + 1 这三个点之外的最优解, 但是如果选择 i - 1,i + 1 这两个点,再去选择其他点可能会更优,口胡想一下,只有这两种方案,因为加入你选了i - 1,你还想选i + x, 这里的i + x 必定是没有 i + 1这个点优秀的。
然后我自己想反悔怎么办,比如我现在选择了i号节点,我将来有可能不选了,选他旁边的i-1 和 i + 1,考虑我们统计答案是讲所有选择的点求一个Sum, 所以想要反悔把当前这个i 削掉就行了,所以我们在插入一个a[i-1] + a[i+1] - a[i] 这么一个值,然后一直维护堆就行了。
这就可以辣,贴个简短代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
#define INF 1e9
/*void dfs(int u,int val){//用了u个电缆,总共价值为val
if(u == k + 1){
ans = min(ans, 1ll*val);
return;
}
for(int i = 1;i <= n;++ i)
for(int j = i + 1;j <= n;++ j)
if(!vis[i] && !vis[j]){
vis[i] = vis[j] = 1;
val += abs(a[j] - a[i]);
dfs(u+1,val);
vis[i] = vis[j] = 0;
}
return;
}
*/
//一个贪心中的重要结论,线性走过去,如果你走过了这个点
//那么你一定不选,因为可以先前路过的时候顺手选上,而不是现在,现在这样
//更劣
int s[N];
int a[N], pre[N], nxt[N], ans;
int n, k;
bool vis[N];
priority_queue <pair<int, int> > q;
int main(){
cin >> n >> k;
for(int i = 1;i <= n;++ i)
cin >> a[i];
for(int i = 1;i < n;++ i){
s[i] = abs(a[i+1] - a[i]);
pre[i] = i - 1;
nxt[i] = i + 1;
q.push(make_pair(-s[i], i));//小根堆trick
}
s[0] = s[n] = INF;//这样小根堆永远不会取到最边界
for(int i = 1;i <= k;++ i){
while(vis[q.top().second])
q.pop();
int x = -q.top().first;
int pos = q.top().second;
q.pop();
ans += x;
int l = pre[pos], r = nxt[pos];//双向链表更新
pre[pos] = pre[l], nxt[pos] = nxt[r];
nxt[pre[pos]] = pos, pre[nxt[pos]] = pos;
vis[l] = vis[r] = 1;
s[pos] = s[l] + s[r] - x;
q.push(make_pair(-s[pos], pos));
}
cout << ans;
return 0;
}