CF1253E Antenna Coverage

一道难度2200的dp题

题意：

街道上有$n$个天线。第$i$个天线的位置为$x_i$ ，以及一个范围值$s_i$ ；第$i$个天线的覆盖范围是$[x_i-s_i,x_i+s_i]$

每次操作，你可以花费1代价，使得第$i$个天线的$s_i$增加一。每个天线都可以进行多次操作。现在请问你最少需要花费多少代价，使$[1,m]$编号内的每一个位置都被至少一个天线覆盖。

题解：

f[i]表示覆盖1~i的最小代价

初始化f[i]=i，因为转移方向从左往右，在不考虑某点右方天线的情况下，最坏都可以看成是从f[0]转移的

转移枚举1~m每个点，再分别对每个点枚举所有天线，分类讨论：

若天线在它左边，由于从左向右转移的原则和局部最优解的性质，就可以不用判能否覆盖，直接从它的最大右覆盖处转移即可

$f[i]=min(f[i],f[max(0,x[j]-s[j]-1)])$

若天线在它右边，则就要从它对于这个天线的左边的对称点转移，如果在天线半径之外，还要加上个代价

$f[i]=min(f[i],f[max(0,2*x[j]-i-1)]+max(0,i-x[j]-s[j]))$

答案是f[m]

如果无法理解转移，可以看看下面这张图，是我从这里偷来的qwq

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int n,m,x[N],s[N],f[N];

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++) read(x[i]),read(s[i]);
    for(int i=1;i<=m;i++) f[i]=i; //初始化
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++){
            if(i>=x[j])
                f[i]=min(f[i],f[max(0,2*x[j]-i-1)]/*对称点处*/+max(0,i-x[j]-s[j])/*若超出还要补上额外代价*/); //在天线右边
            else
                f[i]=min(f[i],f[max(0,x[j]-s[j]-1)]/*因为局部最优解，所以可以直接从边界转移*/); //在天线左边
        }
    write(f[m]);
}