[CODEFORCES 1253E Antenna Coverage](https://codeforces.com/contest/1253/problem/E)
=

## 題目大意
$[1, m]$ 數線上有 $n$ 根天線
每根天線位置 $x$ 有其範圍 $s$，將涵蓋 $[x-s, x+s]$ 區間
將範圍過擴大 $k$ 範圍會花費 $k$ 使涵蓋變為 $[x-s-k, x+s+k]$ 區間

目標是將 $[1, m]$ 都涵蓋

## 輸入
$n$ 與 $m$
及 $n$ 對 $x$ 和 $s$
## 輸出
最小花費

## 解法 1
由於需要決策使哪些天線成長，並且評估**最小**的花費
考慮看看這是不是個 DP 問題

細看問題，須將涵蓋的範圍遍及每個點，而每個點都知道被哪根天線覆蓋
> 但對我們而言是哪根並不重要

先試試粗暴的定義狀態 $\text{dp}(i)$ 就是涵蓋 $[1, i]$ 範圍的最小成本
若是有這個狀態，再配合一根天線區間會到 $j$ 的，那麼也能直接求得 $\text{dp}(j)$ 的解

而明顯的，一但 $\text{dp}(i)$ 被解出來，$\forall j>i.\text{dp} (j)$ 的解並不干擾 $\text{dp}(i)$

接著設計狀態轉移，
對於**固定**點 $i$，$\text{dp}(i)$ 僅需顧好範圍 $[1, i]$
看極端例子，若 $s = 0$，則只看 $x$ 的位置在哪就好
<!-- 若 $x$ 在 $i$ 的右側，花費 $i$
> 因為天線跑出 $[1, i]$ 違反題目條件，但為求解較 $i$ 大的問題，需要這個花費 -->

- 若 $x$ 在 $i$ 的左側，花費 $i - x$ 再加上 $x - 1$
- 若 $x$ 在 $i$ 上，花費 $x - 1$
> $-1$ 表示扣除天線本身位置

而 $s > 0$ 的話，就看 $[x-s, x+s]$ 這整個範圍是落在 $i$ 的左側還是裡面
- 在左側，花費為 $i-(x + s)$ 再加上 $\max(x - s - 1, 0)$
- 在裡面，花費為 $\max(x - s - 1, 0)$
> $x - s - 1$ 有可能會跑到範圍 $1$ 之外

靠 $\text{dp}(i)$ 要解出 $\forall j>i.\text{dp} (j)$，最差的狀況就是沒有天線預設涵蓋 $\text{dp}(i)$，所以初始化為 $i$
> 可以想像有天線涵蓋 $j$ 但不涵蓋 $i$ 的狀況，那麼花費就是 $i$ 到 $x-s$ 加上 $\text{dp}(i)$

#include<bits/stdc++.h>
using namespace std;

int const maxn = 90;

int n, m, x[maxn], s[maxn];

int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &s[i]);

  vector<int> dp(m+1);
  iota(dp.begin(), dp.end(), 0);

  for(int i = 1; i <= m; i++) {
    for(int j = 0; j < n; j++) {
      if(i > x[j]+s[j])
        dp[i] = min(dp[i], dp[max(0, x[j]-(i-x[j])-1)] + i-(x[j]+s[j]));
      else
        dp[i] = min(dp[i], dp[max(0, x[j]-s[j]-1)]);
    }
  }

  printf("%d\n", dp[m]);

  return 0;
}

## 解法 2
$\text{dp}(i)$ 的狀態定義與解法 1 一樣
但在計算上，在遍歷到點 $i$ 上時會以早已解出 $\text{dp}(i)$ 為前提做狀態轉移

且事先加上已知的解 $\text{dp}(0) = 0$，為了那些預設已經涵蓋到 $i=1$ 的天線

#include<bits/stdc++.h>
using namespace std;

int const maxn = 90;

int n, m, x[maxn], s[maxn];

int main()
{
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d%d", &x[i], &s[i]);

  vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int a, int b) {
    if(x[a] == x[b]) return s[a] < s[b];
    return x[a] < x[b];
  });

  vector<int> dp(m+1);
  iota(dp.begin(), dp.end(), 0);

  for(int j: idx) {
    for(int i = 0; i <= m; i++) {
      int g = max(0, x[j]-s[j]-1 - i); // gap
      int r = min(m, x[j]+s[j]+g); // right
      dp[r] = min(dp[r], dp[i]+g);
    }
  }

  int best = m-1;
  for(int i = 1; i <= m; i++) best = min(best, dp[i] + m-i);
  printf("%d\n", best);

  return 0;
}

## 解法 3
- 若一支天線與另一支天線的範圍互相重疊或碰觸，那麼可將他們看作**一支範圍更大的天線**
- 而對於一支天線，花成本升級就能看作產生另**一支範圍更大的天線**

也就是說只要將所有種**覆蓋整個街道的天線**產生，看**哪個成本低**就行了
>如何有效率的產出覆蓋整個街道的天線？

街道從左至右，每遇到一個天線，就看他範圍內有沒有別的天線能碰到 $1$ 位置，如果有就將他跟這個天線合成為一支範圍更大的天線
而明顯的，眾多選擇中只要每次挑的天線成本最低，那麼合成的天線一定成本低
這樣一路合成天線到最右端 $m$，就能得到成本最低且覆蓋整個街道的天線。

實作採用線段樹，因為複雜度較小，細節請參考標準程式

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e5 + 10;
int const INF = 0x3f3f3f3f;

int n, m;
vector<pair<int, int>> ant[maxn];

struct node {
  int cost;
  node *lc, *rc;
  node() { cost = 0; lc = rc = NULL; }
};

node* build(int L, int R) {
  node *u = new node();
  if(L != R) {
    int M = (L+R) / 2;
    u->lc = build(L,   M);
    u->rc = build(M+1, R);
  }

  return u;
}

int query(node *u, int L, int R, int qL, int qR) {
  if(R < qL || qR < L) return INF;
  if(qL <= L && R <= qR) return u->cost;

  int M = (L+R) / 2;
  return min(query(u->lc, L, M, qL, qR), query(u->rc, M+1, R, qL, qR));
}

int update(node *u, int L, int R, int i, int cost) {
  if(i < L || R < i) return u->cost;
  if(L == R) return u->cost = cost;

  int M = (L+R) / 2;
  return u->cost = min(update(u->lc, L, M, i, cost), update(u->rc, M+1, R, i, cost));
}

int main()
{
  scanf("%d%d", &n, &m);

  while(n--) {
    int x, s;
    scanf("%d%d", &x, &s);

    if(x-s <= 1 && m <= x+s) { puts("0"); return 0; }

    for(int cost = 0; 1 <= x-s || x+s <= m; s++, cost++) // 將此天線能升級出的所有天線產出
      ant[min(x+s, m)].emplace_back(max(x-s, 1), cost); 
  }

  node *root = build(1, m);
  for(int i = 1; i <= m; i++) {
    int best = INF;
    for(auto [qL, cost]: ant[i]) // 範圍 [qL, i] 的天線成本為 cost
      best = min(best, query(root, 1, m, qL, i) + cost); // 選擇範圍中有重疊或碰觸的成本最小天線

    if(i == m) printf("%d\n", best);
    update(root, 1, m, i+1, best); // 若其他天線範圍有 i+1 則能與這個成本為 best 的天線合成
  }

  return 0;
}