Luogu P2519 [HAOI2011]problem a

\(DP\)神题。以后要多学习一个，练一练智商。

关键点在于把“有\(a_i\)个人分数比我高，\(b_i\)个人分数比我低”这句话转换成“排名为\(a_i+1\)，且有\(n-a_i-b_i\)个人和我分数相同“。解决了这一点，问题就解决了一大半，接下来就变成了最大不相交区间集合选择问题。本来我是用最长路写的，不知道为什么出锅了，所以就改用\(DP\)+二分了。

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct Segment {

    int l, r, sz;

    Segment (int _l = 0, int _r = 0, int _sz = 0) {

        l = _l, r = _r, sz = _sz;

    }

    bool operator < (Segment rhs) const {return l == rhs.l ? r < rhs.r : l < rhs.l;}

    bool operator == (Segment rhs) const {return l == rhs.l && r == rhs.r;}

} arr[N];

map <Segment, int> mp;

int n, a[N], b[N], tot, dp[N], dis[N], vis[N];

bool cmp (Segment lhs, Segment rhs) {return lhs.r == rhs.r ? lhs.l < rhs.l : lhs.r < rhs.r;}

int main () {

    cin >> n;

    for (int i = 1; i <= n; ++i) {

        cin >> a[i] >> b[i];

        if (a[i] + b[i] <= n - 1) {

            arr[++tot] = Segment (a[i] + 1, n - b[i], n - a[i] - b[i]);

            mp[arr[tot]]++;

        }

    }

    sort (arr + 1, arr + 1 + tot);

    tot = unique (arr + 1, arr + 1 + tot) - arr - 1;

    for (int i = 1; i <= tot; ++i) {

        mp[arr[i]] = min (mp[arr[i]], arr[i].sz);

        // printf ("Segment %d = [%d, %d]\n", i, arr[i].l, arr[i].r);

    }

	sort (arr + 1, arr + 1 + tot, cmp);

	for (int i = 1; i <= tot; ++i) {

		dp[i] = max (dp[i], dp[i - 1]);

		int l = 1, r = i;

		while (l < r) {

			int mid = (l + r + 1) >> 1;

			if (arr[mid].r < arr[i].l) {

				l = mid;

			} else {

				r = mid - 1;

			}

		}

		dp[i] = max (dp[i], dp[r] + mp[arr[i]]);

	}

	cout << n - dp[tot] << endl;

}

巴特西

Luogu P2519 [HAOI2011]problem a

最新文章

热门文章