数据备份

发表于 | 分类于 | 评论数： | 阅读次数：

题目

这是题目

思路

看书做的这道题。

首先可以想到最优解的配对方案定是选择相邻的两个点配对。（二分图匹配？）

记$i$号点与$i-1$号点的距离为$d[i]$ ，题目就是要求这$n-1$个数中选$k​$个数且选择的数不相邻，所有数总和的最小值。（DP？？）

正解当然就是我们最方便的堆！！！

先看K=1时：答案就是d数组的最小值。

当K=2时： 设$d_{min}$ 的下标为$x​$ 。

答案就是$d[x]$ + 除去$d[x-1],d[x],d[x+1]$剩下数的最小值，

或$d[x-1]+d[x+1]$。

用书上的证明：

如果$d[x-1]$和$d[x+1]$都没选，那么不选$d[x]$一定不优；如果在$d[x-1]$和$d[x+1]$中选了一个，那把那个换成$d[x]​$一定更优，所以最优解就一定在这两个之中。

以上和堆没有关系啊

可以得到推论：最小值两边的数要么都选要么都不选。

因此我们可以先选最小值$d[x]$,再删除$d[x-1],d[x],d[x+1]$，再插入$d[x-1]+d[x+1]-d[x]$（一个“反悔”操作）

整体上就删去了一个数，问题变为了$n-1$个数中选$k-1$个数的子问题了。

这样一直做$k​$次就好了。

有一个细节就是$d[0]$和$d[n]$要为一个极大值，保证不受两端的影响。

再之后用链表和堆来维护就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;
inline int read(){
    int x=0,f=1;char C=getchar();
    while(!isdigit(C)) {if(C=='-') f=-1;C=getchar();}
    while(isdigit(C)) x=(x<<1)+(x<<3)+C-'0',C=getchar();
    return x*f;
}
int n,k,d[maxn],a[maxn];
int L[maxn],R[maxn],ans;
bool vis[maxn];
priority_queue<pair<int,int> >que;
#define mk make_pair
inline void Del(int x){
    L[x]=L[L[x]],R[x]=R[R[x]],
    L[R[x]]=x,R[L[x]]=x;
}
int main(){
//	freopen("1.in","r",stdin);
    n=read(),k=read();
    for(int i=1;i<=n;i++)
      d[i]=read(),a[i-1]=d[i]-d[i-1],
      L[i]=i-1,R[i]=i+1;
    a[n]=a[0]=1<<28;
    for(int i=1;i<n;i++) que.push(mk(-a[i],i));
    while(k&&que.size()){
        int u=que.top().second; que.pop();
        if(vis[u]) continue;
		ans+=a[u]; k--;
        int pre=L[u],nxt=R[u];
        vis[pre]=vis[nxt]=1;
        Del(u);
		a[u]=a[pre]+a[nxt]-a[u];
        que.push(mk(-a[u],u));
        
    } printf("%d",ans);
    return 0;
}