时间戳

首页 > 解决方案 > 代码部队 607A。得到错误的答案

data-structures - 代码部队 607A。得到错误的答案

问题描述

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

这是问题的链接 ( http://codeforces.com/contest/607/problem/A ) 问题的屏幕截图。
我的方法是使用 Dp 查找未销毁的最小对象数。如果我只有 i 个元素，则 dp[i]= 未销毁的最小对象数。
- 当第 i 个对象被右侧的某个元素破坏时，令inc为答案。因此， 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 = long long int
pll = pair of long int
rep(i,0,n) = loop from 0 to 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

标签： data-structuresc++14dynamic-programming

解决方案

问题

这就是您定义的方式dp[i]：

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

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

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

其次，如果你只有i个元素，那么第i 个元素永远不会被其右侧的任何信标破坏（因为没有任何信标）。因此，考虑第i 个信标被其右侧的某物破坏的情况是愚蠢的。

解决方案在于重新表述您的子问题 ( dp[i])。

解决方案#1

让我们dp[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];

注意： 最多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 个信标时，可能会发生以下两种情况之一：

  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];

为了解决这个问题，必须找到最大值 dp[i]：

// minimum_number_of_beacons_destroyed = n - maximum_number_of_beacons_lit

这是我的“已接受”解决方案，基于您的代码和此提交。

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

附加说明：

  • Genos 添加的信标是无关紧要的——他总是可以将其放置在尽可能远的右侧，以免影响任何现有的信标，这就是为什么该信息不会增加问题的原因。
  • 信标必须事先按位置升序排序。

推荐阅读