题目地址：洛谷：【P2519】[HAOI2011]problem a – 洛谷、BZOJ：Problem 2298. — [HAOI2011]problem a

题目描述

一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)

输入输出格式

输入格式：
第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、bi

输出格式：
一个整数，表示最少有几个人说谎

输入输出样例

输入样例#1：

3
2 0
0 2
2 2

输出样例#1：

1

说明

100%的数据满足： 1≤n≤100000 0≤ai、bi≤n

题解

不好求最少说谎人数，转而求最大没说谎人数。
考虑说谎是怎么说的：

1. 对于说自己前面有a人，后面有b人且a+b+1>n的人，他肯定在说谎，直接跳过它
2. 对于所有说自己前面有a人，后面有b人的人，如果人数超过了n-a-b，那么人数-(n-a-b)这些人肯定在说谎

第一个可以在读入的时候顺手处理了，而第二个需要用动态规划。
把每个前面有a人，后面有b人的信息处理成成绩所在的区间为[a+1, n-b]这样的形式，并统计这个区间上实际有多少人，问题就变成了，每个区间有一个权值，选择不重叠的区间让权值最大。这个可以用DP做，令dp[i]表示选择完[1, i]这里面的区间后，权值和最大的值。对于右端点i，我可以不选区间，则从dp[i-1]转移而来；选择区间，则从选择的区间的左边转移而来，也就是说
\displaystyle dp[i] = \max \begin{cases} dp[i-1] & \text{不选择右端点为i的区间} \\ dp[\text{选择区间左端点}-1] + \text{选择区间的权值} & \text{选择右端点为i的区间} \end{cases}
我们用一个vector数组，vec[i]表示右端点为i的区间的左端点集合，这样就可以遍历该vector实现转移了。而权值的统计，实际上是输入数据中每个区间的出现次数，用个map搞一搞。注意如果权值超过区间长度，要跟区间长度取个min。

代码

学习了一波题解 P2519 【[HAOI2011]problem a】 – rushcheyo 的博客 – 洛谷博客的写法，感谢这位同学。

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

#include <algorithm>
#include <vector>
#include <map>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n;

struct Node {
    int s, t;
    inline bool operator<(const Node &rhs) const {
        return t == rhs.t ? s < rhs.s : t < rhs.t;
    }
};

std::vector<int> vec[MAXN];
std::map<Node, int> cnt;

int dp[MAXN];

int bef, aft;

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        bef = readint(); aft = readint();
        if(bef + aft + 1 > n) continue;
        if(++cnt[Node {bef + 1, n - aft}] == 1) {
            vec[n - aft].push_back(bef + 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1];
        for(int j = 0; j < vec[i].size(); j++) {
            dp[i] = std::max(dp[i], 
                dp[vec[i][j] - 1] + std::min(i - vec[i][j] + 1, cnt[Node {vec[i][j], i}]));
        }
    }
    printf("%d", n - dp[n]);
    return 0;
}