Codeforces 607A。得到错误答案

Question

在一条数字线上有n个位于不同位置的信标。第i个信标具有位置A_i和功率电平B_i。当第i个信标被激活时，它摧毁其左侧（坐标递减方向）距离bi（含）内的所有信标。然而，信标本身并没有被摧毁。埼玉县将从右至左一个一个地启动信标。如果一个信标被破坏，它就不能被激活。
埼玉希望Genos在所有现有信标的右边严格地添加一个信标，具有任何位置和任何功率等级，这样尽可能少的信标被破坏。注意，Genos放置的信标意味着它将是第一个被激活的信标。帮助Genos找到最小数量的信标可以被摧毁。

这里是问题的链接（http://codeforces.com/contest/607/problem/a)。
我的方法是使用Dp找到最小数量的未销毁的对象。DP[i]=如果我只有i个元素，则未销毁的对象的最小数目。
-让inc是当第i个对象被位于右侧的某个元素销毁时的答案。因此inc=1+DP[i-1]

-让exc是当第i个对象未被位于右侧的某个元素销毁时的答案。由于第i个元素没有被摧毁，当我们将其引爆时，它将摧毁其左限范围内的所有元素(A[i]-B[i])。假设它可以破坏左侧的lbd个元素。因此exc=lbd+dp[i-lbd]。

现在dp[i]=min{inc,exc}。最后返回dp[n]。

但是我的代码在测试用例11中给出了错误的答案。如果我的逻辑或代码有问题，谁能帮助我吗？
这是我的代码片段
ll=long long int
pll=pair of long int
rep(i,0,n）=从0到n的循环

void solve(){
    ll n;
    cin>>n;
    vector<pll> a(n);
    vector<ll> b(n);
    rep(i,0,n){
        cin>>a[i].first>>a[i].second;
        b[i]=a[i].first;
    }
    sort(b.begin(),b.end());
    sort(a.begin(),a.end(),cmp);
    vector<ll> dp(n+1,0);
    rep(i,1,n+1){
        ll inc = 1+ dp[i-1];
        ll temp = a[i-1].first-a[i-1].second;
        ll lb = lower_bound(b.begin(),b.end(),temp)-b.begin();
        ll exc=(i-lb-1)+dp[lb];
        dp[i]=min(inc,exc);
    }
    cout<<dp[n]<<endl;
}

完整代码链接https://ideone.com/thbclk

Answer 1

这就是您如何定义DP[i]:

dp[i]=如果我只有i个元素，则未销毁的对象的最小数量。

首先，我认为这是一个错别字，你的意思是：

// dp[i] ... The number of beacons destroyed after lighting the i-th beacon

当我们点亮第I个灯塔：

1. 它会摧毁其功率范围内的所有信标。
2. 某些信标可能在此之前已经被破坏，未受第i个信标的影响。

合并%1。和2。我们得到dp[i]的以下表达式：

// lb = Lower Bound - the index of the left-most beacon
// that is still in the power range of the i-th beacon
dp[i] = lb == 0 ? i : i - lb + dp[lb-1];

ll ans = n - 1;
rep(i, 0, n) {
    ans = min(dp[i] + n - i - 1, ans);
}

// dp[i] ... The number of beacons lit after lighting the i-th beacon

当我们点亮第i个灯塔时，可能会发生两件事之一：

1. 第i个信标是如此强大，它杀死了它左边的所有信标，使它成为唯一被点亮的信标
2. 第i个信标只会击倒其左侧的一些信标

合并%1。和2。我们得到dp[i]的以下表达式：

// lb = Lower Bound - the index of the first beacon left of the
// i-th beacon that is out of the power range of the i-th beacon
dp[i] = lb < 0 ? 1 : 1 + dp[lb];

// minimum_number_of_beacons_destroyed = n - maximum_number_of_beacons_lit

null