【动态规划】bzoj2298: [HAOI2011]problem a

建模超级妙……

Description

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

Input

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

Output

一个整数，表示最少有几个人说谎

Sample Input

3
2 0
0 2
2 2

Sample Output

HINT

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

题目分析

一开始真的真的没看出来是个dp……

口胡做法

口胡了一个做法：给每一个人确定一个排名（若分数相同那么排名相同），然后用一些神奇的方法去考虑这些排名是否不互相矛盾。还考虑了一下不矛盾性可不可以递移（最近学了tarjan所以看什么都是图论）……然而发现并不可做。

正经做法

如果考虑分数相同的问题，那么每一个人的排名其实可以看做一个区间$[l,r]=[a_i+1,n-b_i]$。首先考虑哪些话必假：1.$l>r$；2.排名区间为$[l,r]$的个数大于$r-l+1$，此时$[l,r]$只能有$r-l+1$个。又因为答案不要求输出方案，所以只需要取够$r-l+1$就行了，而不用管到底取了哪些区间。

把每一个人都映射成区间之后，我们来观察一下很多相同区间的情况。也就是说，有很多人的排名相同的情况。

可以发现他们是互不影响的。比如我说我排名是$[1,5]$里的，你说你也是$[1,5]$里的，那么我和你的话是不冲突的。可以同时认定我们说的话是真话并且对于其他的选择来说没有干扰————既然这样，何不把$v$个区间$[l,r]$再次映射成一条有权值$v$的线段呢？这里线段的权值代表：认同“$[l,r]$这段区间里的人分数相同”是真话所能够获得的人数。

于是问题就转化为了：

有若干条带权值的线段$[l,r]$，要求选出互不重叠的一些，使得所选线段权值和最大。

这样就是dp问题了。

正经做法的疑问？

但是这样如何能够保证：选了的$[l,r]$是合法的？

换而言之，“$[l,r]$这段区间里的人分数相同”这句话如果要成立，那么不仅仅是要求有那么一两个人说自己在这个区间里，还要求总共有$r-l+1$个人都是在这个区间里。

嘛，我们还有那些说假话的人么。所以只要把他们安排在需要人的地方就行了。

但是如何保证说假话的人足够多，以至于能够满足我们钦定的真话呢？

这样想似乎非常抽象并且非常复杂，但实际上形象一点理解就很自然了。这里陈述两个基本事实：

每一个人无论说了真话还是假话最终都会有一个排名
每一个人说的话占的排名最多长度为$n$

那么所有钦定的真话最长也就只有$n$，因为钦定的话不会互相重叠。又因为说话的人自己会算作一次，所以一定是够填的。

注意

还有注意就是，那个dp时候用的是$lower\_bound$……突然脑抽用了$upper\_bound-1$发现只有90……

 1 #include<bits/stdc++.h>
 2 typedef std::pair<int, int> pr;
 3 const int maxn = 100035;
 4 
 5 struct seg
 6 {
 7     int l,r,v;
 8     bool operator < (seg a) const
 9     {
10         return r < a.r;
11     }
12     seg(int a=0, int b=0, int c=0):l(a),r(b),v(c) {}
13 }a[maxn];
14 int n,f[maxn],d[maxn],tot;
15 std::map<pr, int> mp;
16 
17 int read()
18 {
19     char ch = getchar();
20     int num = 0;
21     bool fl = 0;
22     for (; !isdigit(ch); ch = getchar())
23         if (ch=='-') fl = 1;
24     for (; isdigit(ch); ch = getchar())
25         num = (num<<1)+(num<<3)+ch-48;
26     if (fl) num = -num;
27     return num;
28 }
29 int main()
30 {
31     n = read();
32     for (int i=1; i<=n; i++)
33     {
34         int ax = read(), bx = read();
35         int l = ax+1, r = n-bx;
36         if (l > r) continue;
37         pr tt = std::make_pair(l, r);
38         if (mp[tt]==r-l+1) continue;
39         if (!mp[tt])
40             a[++tot] = seg(l, r, 0);
41         mp[tt]++;
42     }
43     for (int i=1; i<=tot; i++)
44         a[i] = seg(a[i].l, a[i].r, mp[std::make_pair(a[i].l, a[i].r)]);
45     std::sort(a+1, a+tot+1);
46     for (int i=1; i<=tot; i++) d[i] = a[i].r;
47     for (int i=1; i<=tot; i++)
48     {
49         int tt = std::lower_bound(d+1, d+i, a[i].l)-d-1;
50         f[i] = std::max(f[i-1], f[tt]+a[i].v);
51     }
52     printf("%d
",n-f[tot]);
53     return 0;
54 }