题解 CF1253E 【Antenna Coverage】

· · 题解

在我的博客园看效果更佳：点这里

本题难点在正确性证明，所以写个我尽力写出的证明严谨（？）的题解。

令 f_i 表示 [1,i] 被全部覆盖的最小花费。答案为 f_m。

首先发现，添加一个区间 [0,0] 不会影响答案。所以 f_i 的初值可以设为 i。（这个很重要，没了就不对了！）

转移，如果 i 已经被某个初始区间完全覆盖了，那么可以从 f_{i-1} 转移来。

然后枚举每个区间，如果区间的右端点在 i 左边，计算把这个区间扩张到能恰好覆盖到 i 后的左端点。也就是从 f_{\max(0,l[j]-(i-r[j]))}+i-r[j] 转移来。

记下每个区间被扩张成什么样会炸状态，所以直接从初始的区间开始扩张。

时间复杂度 O(nm)。

开始证明正确性。

首先证明只用考虑被左边的区间覆盖，不需要考虑右边的。

其实被右边的区间覆盖也被考虑过了，不过转移的时候就直接跳过了这些点（在这个被扩张后的区间中）。所以不用管。

接下来证明直接从初始的区间开始扩张就是最优解。

如果需要在被扩张的区间的基础上继续扩张，说明这次扩张到的点 i 一定在上次扩张到的点 j 的右边，扩张到 i 后的区间的左端点一定跳过了 j。而我们最后要用到的是 i 的状态（因为需要继续扩张），所以中间这第一次扩张是没有必要的。

所以这种情况不可能发生。

接下来证明恰好扩张到能覆盖 i 就是最优解，也就是最优解不需要扩张到覆盖超过 i 一点点。

如果需要扩张更多，一定是因为可以覆盖左边的更多点，让左边的区间更短（不然覆盖到超过 i 的位置在 f_i 是完全没有必要的）。

但是由于添加了区间 [0,0]（没错，它的作用就在这），一定有 f_{i+1}\le f_i+1（因为覆盖到 i 的区间可以再扩展一格）。

所以跳过区间后的转移点应该是越右越好。也就是不需要扩展到 i 右边。

于是这个就是对的了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100010;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
    char ch=getchar();ll x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
int n,m,x[maxn],s[maxn],f[maxn]; 
int main(){
    n=read();m=read();
    FOR(i,1,n) x[i]=read(),s[i]=read();
    f[0]=0;
    FOR(i,1,m){
        f[i]=i;
        bool flag=false;
        FOR(j,1,n) if(x[j]+s[j]>=i && x[j]-s[j]<=i) flag=true;
        if(flag) f[i]=f[i-1];
        FOR(j,1,n) if(x[j]+s[j]<i) f[i]=min(f[i],f[max(0,2*x[j]-i-1)]+i-(x[j]+s[j]));
    }
    printf("%d\n",f[m]);
}