有n个激光塔排成一行，第i个激光塔的位置为ai，威力是bi，当第i个激光塔被激活后，所有在这个激光塔左边且与该激光塔距离小于等于bi的激光塔都会被摧毁，而该激光塔本身不会受到伤害。管理员从右向左依次激活每个激光塔，如果一个激光塔被摧毁了，则它无法被激活。 现在管理员想让你帮他一个忙，管理员决定在现有的n个激光塔的右边再放一个激光塔，这个激光塔的位置和威力是任意的（但必须在现有激光塔的右边）。管理员从这个新加入的激光塔开始从右到左依次激活每个激光塔，现在他想要知道，怎么安排这个新激光塔，可以使得被摧毁的激光塔的总数最少。

题解：dp
dp[i][0] 表示位置i灯塔不摧毁
dp[i][1] 表示位置i当前灯塔摧毁
所以转移方程为
dp[i][1] = dp[i - 1][0] + 1
dp[i][0] = dp[i - b[i] - 1][0] + sum[i - 1] - sum[i - b[i] - 1]
(sum[i]表示前缀激光灯的数量)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int maxm = 1e6+1;
int a[maxn];
int dp[maxn][2];
int sum[maxn];
int main() {
    int n;
    int t1, t2;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> t1 >> t2;
        t1++;
        a[t1] = t2;
    }
    for (int i = 1; i <= maxm; i++) sum[i] = sum[i - 1] + (a[i] != 0);
    for (int i = 1; i <= maxm; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        if (a[i]) {
            //dp[i][0]  表示当前灯塔不摧毁
            //dp[i][1] 表示当前灯塔摧毁
            //dp[i][1] = dp[i - 1][0] + 1;(如果当前激光灯已经被摧毁，则下一个激光灯一定是激活激活状态
//            cout << i << " " << i - a[i] - 1 << " " << sum[i - 1] - sum[i - a[i] - 1] <<endl;
            if (i - a[i] > 0) {
                dp[i][0] = dp[i - a[i] - 1][0] + sum[i - 1] - sum[i - a[i] - 1];
            } else {
                dp[i][0] = sum[i - 1];
            }
        }
//        cout << i << " "; cout << dp[i][0] << " " << dp[i][1] << endl;

    }
    int ans = 1e9;
    for (int i = 1; i <= maxm; i++) {
        int t = sum[i];
        ans = min(ans, min(dp[i][0], dp[i][1]) + n - t);
    }
    cout << ans << endl;
    return 0;
}