Codeforces Round #336 (Div. 1) A. Chain Reaction

Codeforces Round #336 に参加しました。相変わらず D が解けないおじさん。

問題

codeforces.com

解法

右から r 個の ビーコンを消す時, 残りのビーコンのうち何個のビーコンが破壊されずに残るのかが分かれば, 最高でビーコンがいくつ残るのかがわかります。そこで, dp[i] = (i 番目のビーコンが残っている時, i 番目及びそれより左のビーコンのうち何個のビーコンが破壊されずに残るか) という dp を考えます。

i 番目のビーコンについて, a[i]-b[i] の lower_bound を取れば, i 番目より左のビーコンで破壊されずに残る, 最も右側のビーコンがどこにあるのかがわかります。このビーコンについて, さらに再帰的に処理していけば dp[i] を求めることが出来ます。

const int MAXN = 100010;
pii P[MAXN];
int dp[MAXN];
int n;

int dfs(int now) {
    int& ret = dp[now];
    if (ret >= 0) return ret;
    if (now == 0) return ret = 1;
    ret = 1;
    pii q = pii(P[now].first-P[now].second, 0);
    int l = lower_bound(P, P+n, q) - P;
    if (l == 0) return ret;
    return ret = 1+dfs(l-1);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> P[i].first >> P[i].second;
    }
    sort(P, P+n);
    memset(dp, -1, sizeof(dp));
    for (int i = n-1; i >= 0; i--) {
        if (dp[i] == -1) {
            dfs(i);
        }
    }
    int maxi = 0;
    for (int i = 0; i < n; i++) {
        maxi = max(maxi, dp[i]);
    }
    cout << n-maxi << endl;
    return 0;
}