SP1553 BACKUP - Backup Files

Let_Fly · 2023-09-12 13:06:42 · 题解

SP1553 BACKUP - Backup Files

思路：

此题和 P1792 几乎一模一样，下面就说说为什么一模一样。

首先我们观察到，恰好选 k 对，贪心地想，电缆一定是连接相邻两座楼的，并且对于一栋楼，左和右只能选一个或都不选，这就是 种树 的描述。然后我们对楼的距离做差分，这个就是单个花费。

考虑到 dp 有一维是限制个数，所以很容易想到要去 wqs 二分。

wqs 二分可以把限制条件转化为二分来降低时间复杂度。

此题中我们可以在满足线缆强制恰好选择了 k 个情况下总价值最小。

如果不考虑强制恰好选择了 k 个这个条件，我们只考虑总价值最小，我们能够得到一个 O(n) 的简单 dp。

现在考虑二分一下所有线缆的额外代价，修改代价后重新进行 dp，顺便记录一下价值最大的情况下选择了多少条线缆。

然后根据选择了多少条线缆来调整二分边界。

最后最优情况是恰好选择 k 条线缆时，我们把额外代价的影响去掉就是正确代价。

故总复杂度是 O(n\log n)。

接下来请看有详细注释的代码。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;

int T,n,k;
int a[N],val[N];
int maxx=LONG_LONG_MIN;
int xmx,xas,ans=-1;
int dp[N][2],cnt[N][2];//考虑到第i个，前一个选没选的最好答案和选了的段数

void check(int v){
    memset(dp,0,sizeof dp);
    memset(cnt,0,sizeof cnt);
    dp[1][1]=val[1]-v,cnt[1][1]=1;
    for(int i=2;i<=n;i++){
        dp[i][1]=dp[i-1][0]+val[i]-v;
        dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
        cnt[i][1]=cnt[i-1][0]+1;
        cnt[i][0]=(dp[i-1][1]<dp[i-1][0]?cnt[i-1][1]:cnt[i-1][0]);
    }
    if(dp[n][1]<dp[n][0]){
        xmx=dp[n][1];
        xas=cnt[n][1];
    }else{
        xmx=dp[n][0];
        xas=cnt[n][0];
    }
}

signed main(){
    cin>>T;
    while(T--){
        xmx=0,xas=0,ans=-1;
        memset(a,0,sizeof a);
        memset(val,0,sizeof val);
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        n--;
        for(int i=1;i<=n;i++){
            val[i]=a[i+1]-a[i];
        }
        int l=0,r=1e9;//本蒟蒻也不会上下界
        while(l<=r){
            int mid=l+r>>1;
            check(mid);
            // cout<<xmx<<' '<<xas<<' '<<mid<<'\n';
            if(xas<=k){
                ans=xmx+mid*k;//其实可以最后更新一次就行，但是为了检验二分成功与否，放在这里
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        if(ans==-1){
            check(0);//没限制就直接拿
            ans=xmx;
        }
        cout<<ans<<'\n';
    }
    return 0;
}