Codeforces 607A。得到错误的答案

Question

有 n 个信标位于数轴上的不同位置。第 i 个信标的位置为 a_i，功率级别为 b_i。当第 i 个信标被激活时，它会销毁其左侧（坐标递减方向）距离 bi（含）内的所有信标。然而，信标本身并没有被摧毁。埼玉将从右到左一次激活一个信标。如果信标被摧毁，它就无法被激活。
埼玉希望杰诺斯严格在所有现有信标的右侧添加一个信标，可以设置任何位置和任何功率级别，从而尽可能减少被摧毁的信标数量。请注意，杰诺斯放置的信标意味着它将是第一个被激活的信标。帮助杰诺斯找到可以摧毁的最少数量的信标。

这是问题的链接（http://codeforces.com/contest/607/problem/A） 。
我的方法是使用Dp来找到未破坏的对象的最小数量。 dp[i]= 如果我只有 i 个元素，则未销毁的对象的最小数量。
- 当第 i 个对象被右侧存在的某个元素破坏时，令 inc 为答案。因此 公司 = 1 + dp[i-1]

- 当第 i 个对象没有被右侧存在的某些元素破坏时，设 exc 为答案。由于第 i 个元素没有被摧毁，当我们引爆它时，它会摧毁其左边界（a[i]-b[i]）内的所有元素。假设它可以破坏左侧 lbd 个元素。因此 exc = lbd + dp[i-lbd].

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

但我的代码在测试用例 11 中给出了错误的答案。如果我的逻辑或代码有问题，任何人都可以帮助我吗？
这是我的代码片段
ll = 长整型
pll = 一对长整型
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] = 被破坏的最小对象数

如果我只有 i 个元素

。

其次，如果你只有

i

元素，那么第 i-th 元素永远不会被其右侧的任何信标摧毁（因为没有信标）。因此，考虑第 i 个信标被其右侧的物体摧毁的情况是愚蠢的。 解决方案在于重新表述你的子问题 (dp[i])。

解决方案#1

让我们这样定义

---

dp[i]

：

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

当我们点亮第

i

信标时：

它会摧毁其功率范围内的所有

信标。

1. 一些信标可能之前已经被摧毁，不受第
i-th
2. 信标的影响。 结合 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];

注意：最多需要摧毁

n-1信标。点亮第 i 个信标后，dp[i] 个信标被摧毁（第 i 个信标左侧的信标），最多仍可摧毁

n-i-1

个信标（第 i 个信标右侧的信标）。

考虑到这一点，这就是最终答案的产生方式：

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

这里

是我的“已接受”解决方案，基于您的代码和

此提交

。 解决方案#2

让我们这样定义

---

dp[i]

：

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

当我们点亮第

i-th

 信标时，可能会发生以下两种情况之一：

第i

信标非常强大，它杀死了左侧的

所有
1. 信标，使其成为唯一点亮的信标 第i信标仅摧毁其左侧
一些
2. 信标 结合 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];

为了解决问题，必须找到

最大值dp[i]

: // minimum_number_of_beacons_destroyed = n - maximum_number_of_beacons_lit

这里

是我的“已接受”解决方案，基于您的代码和

此提交

。 还有一个官方的社论，但是我不清楚该解决方案。

补充说明

：

---

杰诺斯添加的信标是无关紧要的 - 他总是可以将其放置在尽可能右侧的位置，以免影响任何现有的信标，这就是为什么该信息不会增加问题。

信标必须事先按位置升序排序。