CF1408D Searchlights

题意：

在以左下角 \((0 , 0)\) 为坐标原点的直角坐标系中 ， 有 \(n\) 个强盗 \(m\) 个监控。每个监控能看到自己左下角的所有区域。而所有强盗可以且只能同时向右或向上移动一步，求为了让所有强盗摆脱监控，最少移动次数为多少。

解法：

实际上这道题的图最终会形成这样：

观察可知，从上往下 \(x\) 轴能延伸到的位置单调递增。而且在上下两个相邻监控之间的部分，能延伸到的部分相同。

我们开一个数组 \(f_i\) 表示所有海盗先向上走了 \(i\) 步之后，最少要向右走几步。

处理这个数组需要的复杂度为 \(O(nm)\) ，具体实现如下：

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i] > c[j]) continue;
        f[c[j] - a[i]] = max(f[c[j] - a[i]] , d[j] - b[i] + 1);
    }
}

然后再根据 \(x\) 随 \(y\) 单调递减可以得到：

若 \(y\) 越大，那么需要向右平移的位置越少。

所以我们就得到了以下写法：

int ans = 1e9 , last = 0;
for(int i=MAXN;i>=0;i--){
    last = max(last , f[i]);
    ans = min(ans , i + last);
}

时间复杂度：

令 N = 1e6。

总复杂度为 \(O(nm + N)\)

Code