洛谷P2519《[HAOI2011]problem a》

人类智慧题

由于一些原因,不对题面作出展示,请自行寻找

解析

我个人对「人类智慧题」对定义是「运用人脑求特殊解也想不出来的问题」

第一眼看到这题的时候,我一脸问号
直到老师开始讲题……


首先把题目转化一下
对于每个学生,给定了有多少成绩比他好、比他差,那就把数据转换为一个成绩区间,表示这个区间内的人(可能只有 1 个)成绩相同

然后考虑一下「假话」的判断方式

  1. 成绩比他好的 + 成绩比他差的 + 他 > 总人数
    这个请自行理解
  2. 两个有交集的区间没有完全相同,那么两个区间必有一个是假话
    这个很显然吧,就是两个区间有交集的话说明它们是一个成绩,然而小于这个成绩的人或大于这个成绩的人却不相同
  3. 对于一堆完全相同的区间,它们之间是真话的个数至多是[区间长度]个,超出的部分全都是假话
    想一想区间长度的现实意义是什么:有[区间长度]个学生成绩相同。那么,一个成绩是有[区间长度]个人的,也就是说,至多有[区间长度]个属于这个区间对应的成绩的学生在说真话(可以看作他们的成绩属于这个区间对应的成绩),剩下的学生都在说假话。
    这样说应该会好理解一些吧……实在不行我举个例子:[2,4],意味着这个区间对应的成绩有 3 个人获得了,那么如果有 4 个人说“我获得了这个成绩”,那么肯定有 1 个人在说假话。

经过筛选,区间数量减少了一些,再去个重,把相同的区间个数用权值的形式表示出来(对每种区间分配唯一 id),比如说我有三个[2,4]和一个[7,8],我就可以对[2,4]这个区间加一个权值 3,对[7,8]这个区间加一个权值 1。


那么问题现在变成了:带权值的线段覆盖,求最大权值和

这个就是一个 dp 问题了

下面这一段也是从我代码里复制过来的(

1
2
3
4
5
6
7
// 设 F[i] 表示选择右端点不超过 i 的最大权值
// 现实意义就是前 i 个人(按照成绩排序)中有多少人说了真话
// 初始:F[i] = F[i - 1]
// 转移:当 i 点为某一线段的右端点时,
// F[i] = max(F[i], F[j - 1] + Weight)
// 其中 j 为该线段的左端点,Weight 为该线段的权值
// (j - 1) 是因为线段不能重叠

代码实现

代码里有很多注释,应该会很好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//
// LuoguP2519.cpp
// Title: [HAOI2011]problem a
// Alternatives: BZOJ2298
// Debugging
//
// Created by HandwerSTD on 2019/7/29.
// Copyright © 2019 HandwerSTD. All rights reserved.
//

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>

const int MAXN = 100000 + 10;

struct Segment {
int l, r, w;

Segment(int l = 0, int r = 0, int w = 0) : l(l), r(r), w(w) {}
bool operator < (const Segment &that) const {
if (r == that.r) return l < that.l;
return r < that.r;
}
} segt[MAXN];

int Ls[MAXN], Rs[MAXN], Ws[MAXN];
// segt 记录读入后经过处理的线段,Ls, Rs, Ws 记录去重后的线段

int n, cnt, cntnew;
int dp[MAXN];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int l = 0, r = 0;
scanf("%d %d", &l, &r);
// 将给定的数据转化为学生 i 的排名
// 用区间[l,r]的形式表示(按成绩排名)第 l 个人到第 r 个人成绩相同
// 考虑把所有完全相同的线段记为单个带权值的线段
// 那么问题就变为了一个带权线段覆盖问题
if (l + r >= n) continue; // 学生数量不合法,显然是错的
++l; r = (n - ((r + 1) - 1));
// 避免出现左端点为 0 的情况,因为读入的 l 有可能是 0
segt[++cnt] = Segment(l, r); // 记一下目前合法的线段数量
}
std::sort(segt + 1, segt + 1 + cnt);
for (int i = 1; i <= cnt; ++i) {
if (!(segt[i].l == segt[i - 1].l && segt[i].r == segt[i - 1].r)) ++cntnew;
// 两条线段如果重合,就增加该线段的权值
// 两条线段如果不重合,就新开一条线段
// 本质是一个去重并合并权值的过程
Ws[cntnew] = std::min((segt[i].r - segt[i].l + 1), Ws[cntnew] + 1);
// 重合的线段表示有(线段长度)个人是相同成绩的
// 所以每组重合线段(按线段长度分组)的个数如果超过了它的长度
// 则超出去的那部分必定是假话
Ls[cntnew] = segt[i].l; Rs[cntnew] = segt[i].r;
// 记一下去重后的线段
}
for (int i = 1, j = 1; i <= n; ++i) {
// 设 F[i] 表示选择右端点不超过 i 的最大权值
// 现实意义就是前 i 个人(按照成绩排序)中有多少人说了真话
// 初始:F[i] = F[i - 1]
// 转移:当 i 点为某一线段的右端点时,
// F[i] = max(F[i], F[j - 1] + Weight)
// 其中 j 为该线段的左端点,Weight 为该线段的权值
// (j - 1) 是因为线段不能重叠
dp[i] = dp[i - 1];
while (j <= cntnew && Rs[j] == i) {
dp[i] = std::max(dp[i], dp[Ls[j] - 1] + Ws[j]);
++j;
}
}
// 由于 F[i] 表示说真话的数量,所以答案为学生的数量 - 说真话的数量
// 也就是 n - dp[n]
printf("%d\n", n - dp[n]);
return 0;
}