Gym - 101201H

野性酷女 2022-05-14 12:51 108阅读 0赞

![70][]

题意：有k个区间，用他们填满1~n，不允许重叠，问留下的空隙最少是多少

思路：可以从两方面考虑，第一个是正面考虑，转移方程dp\[i\]=min(dp\[j\]+l\[i\]-r\[j\]+1) (r\[j\]<l\[i\])

这样的话将方程移项 dp\[i\]-l\[i\]-1=min(dp\[j\]-r\[j\])，所以用树状数组维护dp\[j\]-r\[j\]的最小值就可以了

为了计算方便，添加一个终点区间（n+1,n+1）

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+10;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    ll n, val[N], s[N], dp[N];
    int k, up;
    struct inter{
        ll l, r;
    }in[N];
    
    bool cmp(inter a, inter b){
        return a.r<b.r || a.r==b.r&&a.l<b.l;
    }
    
    void upd(int x, ll v){
        for(; x<=up; x+=x&-x)
            s[x]=min(s[x], v);
    }
    
    ll query(int x){
        ll ret=INF;
        for(; x>0; x-=x&-x)
            ret=min(s[x], ret);
        return ret;
    }
    
    int main(){
        scanf("%I64d%d", &n, &k);
    
        for(int i=1; i<=k; i++){
            scanf("%lld%lld", &in[i].l, &in[i].r);
            val[i]=in[i].r;
        }
        k++;
        in[k].l=n+1, in[k].r=n+1;
        val[k]=0; val[k+1]=n+1;
        sort(in+1, in+1+k, cmp);
        sort(val+1, val+2+k);
        up=unique(val+1, val+2+k)-val-1;
    
       /* for(int i=1; i<=up; i++) printf("%lld ", val[i]);
        puts("");
    */
        for(int i=1; i<=k; i++){
            ll p=in[i].l-1;
            p=upper_bound(val+1, val+1+up, p)-val-1;
    
            ll mn=query(p);
    
            dp[i]=mn+in[i].l-1;
           // printf("%lld %lld\n", mn, dp[i]);
            p=lower_bound(val+1, val+1+up, in[i].r)-val;
            upd(p, dp[i]-in[i].r);
            //printf("%I64d ", dp[i]);
        }
    
        printf("%lld\n", dp[k]);
    
        return 0;
    }

第二个方面是从反面考虑，这样会是问题非常简单，dp\[i\]是前i个区间覆盖和的最大值

dp\[i\]=max(dp\[j\])+len\[i\]

#include<bits/stdc++.h>
    
    using namespace std;
    typedef long long ll;
    typedef pair<ll, ll> pll;
    const ll N=2e5+10;
    const ll INF=0x3f3f3f3f3f3f3f3f;
    pll p[N];
    ll dp[N];
    
    int main(){
        ll n, k;
        scanf("%lld%lld", &n, &k);
        ll a, b;
        for(int i=1; i<=k; i++){
            scanf("%lld%lld", &a, &b);
            p[i]=pll(b,a);
        }
    
        sort(p+1, p+1+k);
        for(int i=1; i<=k; i++){
            int pr=lower_bound(p+1, p+1+k, pll(p[i].second, 0))-p-1;
            ll tmp;
    
            if(pr==0)
                tmp=p[i].first-p[i].second+1;
            else
                tmp=dp[pr]+p[i].first-p[i].second+1;
            dp[i]=max(tmp, dp[i-1]);
           // cout<<pr<<" "<<dp[i]<<endl;
        }
        printf("%lld\n", n-dp[k]);
        return 0;
    }

[70]: /images/20220514/fdb65bfba87244e89fa070aee70fa03d.png