「Bzoj 2298」「HAOI2011」problem a (DP)

BZOJ 2299
题意：一次考试共有$n$个人参加，第$i$个人说：「有$a_i$个人分数比我高，$b_i$个人分数比我低。」问最少有几个人没有说真话(可能有相同的分数)

没有相同的分数的话就是水题……虽然本题DP好像也挺水的
有相同分数考虑将这个相同分数的区间拎出来($1$到$n$范围内)
设$s(i,j)$为$[i,j]$为相同分数, 有几个人说自己是这个分数。
这个显然可以预处理出来，具体看代码实现
题目所求答案可以补集转化，即求最多有几个人说实话
设$dp(i)$为排名前$i$个人的最多有几个人说实话
那么
$$
dp(i)=\max(dp(i-1),dp(j-1)+\min(i-j+1,s(j,i)))
$$
$j$为当前这个名次的最左边的一个人，即从上一个名次转移过来
这里相当于将每个分数的人按顺序变成几个块来处理。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    map<pair<int, int >, int > ma;
    vector<int > l[MAXN];
    int n, dp[MAXN];

    void clean() {
        ms(dp, 0);
    }
    int solve() {

        clean();
        cin >> n;
        for (int x, y, i = 1; i <= n; ++i) {
            scanf("%d%d", &x, &y);
            ++x, y = n - y;
            if (x <= y) { // [x, y]
                if (++ma[make_pair(x, y)] == 1)
                    l[y].push_back(x);
            }
        }

        for (int i = 1; i <= n; ++i) {
            dp[i] = dp[i - 1];
            for (int o = 0; o < (int)l[i].size(); ++o) {
                int j = l[i][o];
                dp[i] = max(dp[i], dp[j - 1] + min(i - j + 1, ma[make_pair(j, i)]));
            }
        }

        cout << n - dp[n];

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}