洛谷P2519《[HAOI2011]problem a》

七月 30, 2019 3461

人类智慧题

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

解析

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

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

首先把题目转化一下
对于每个学生，给定了有多少成绩比他好、比他差，那就把数据转换为一个成绩区间，表示这个区间内的人（可能只有 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
82
//
//  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;
}