Gym - 101201H-蒲公英云

Gym - 101201H

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

题意：有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;
}