Luogu-P3947-肝活动

Posted on Edited on Word count in article: 2.7k

题目 P3947 肝活动

题目背景

Yume 最近在玩一个名为《LoveLive! School idol festival》的音乐游戏。他之所以喜欢上这个游戏，是因为这个游戏对非洲人十分友好，即便你脸黑到抽不出好卡，还可以通过在每个月举办的两次活动中达成一定的目标来获得奖励。

题目描述

Yume 很喜欢这一期活动奖励卡的卡面，于是他决定要肝这一期的活动，拿到活动奖励。这一期的活动规则很特殊，玩家需要在活动规定的结束时间前，完成所有指定的歌曲（每首歌曲只能打一次），并获得一定的分数，就可以拿到活动奖励。如果在规定的时间前没有完成所有的歌曲，或者分数不够奖励的分数线，则不能领取活动奖励。每首歌有一个限定的奖励开放时间，玩家如果在这段时间内完成了这首歌，便可以获得一定的分数（获得的分数 = 开放时间 - 当前已用的总时间）。如果超出了这段时间之后再完成这首歌，就不能获得分数了。

这样的规则对 Yume 这样的老玩家来说本应是轻而易举，但不巧的是 Yume 把活动的结束时间记成了活动的开始时间，以至于当他上线跃跃欲试的时候，惊恐地发现活动已经快要结束了。现在他想知道，在剩余的时间之内，他能否完成所有的歌、达成奖励的分数线拿到活动卡。为了节省时间，他把这个问题交给了你来解决。请你根据给定的数据，帮他计算出能否在剩余的时间内达成目标。如果能，请告诉他完成每首歌曲的顺序。

输入格式

输入的第一行是三个整数 $n,m,t$，分别表示规定完成的歌曲数目、获得奖励需要达到的最低分数和距离活动结束剩余的时间。

接下来有 $n$ 行，第 $i$ 行有一个字符串 $S_i$ 和两个整数 $T_i$ 和 $M_i$，表示第 $i$ 首歌的歌名为 $S_i$，完成第 $i$ 首歌所需要的时间为 $T_i$，第 $i$ 首歌的奖励开放时间剩余 $M_i$。保证 $T_i\le M_i$。其中数据已按 $S_i$ 的字典序给出。

输出格式

如果在活动结束前 Yume 可以完成指定的目标拿到奖励，则在第一行输出一个整数 $C$，表示在获得奖励的前提下，所能够获得的分数的最大值；

接下来的 $n$ 行中，按照完成歌曲的顺序输出第 $i$ 首歌的歌名。如果有多种可能性，则输出字典序最小的情况。

如果在活动结束前 Yume 不能完成所有的歌曲，输出 No Answer。

思路：状压dp

老熟人了~

$n$ 范围较小，状压dp可用！

基本定义

$state$ 为状态，当它的第 $i$ 位为 $1$ 时，表示第 $i$ 首歌打过了。

$dp[state]$ 表示状态为 $state$ 时的最高分数，$time_[state]$ 表示状态为 $state$ 时的总用时。

$name[state]$ 表示状态为 $state$ 时的歌名（$state$ 只有一位为 $1$）。

$rest[i]$ 和 $need[i]$ 分别表示第 $i$ 首歌的剩余时间和打完需要的时间。

使用 $all_vis_state$ 表示所有歌都打过的时候的状态。

注意：以上定义不完整，因为本题有一部分定义不能看题面就想出，所以需要用的时候即时定义。

本篇会定义或使用一些工具函数，篇尾会提及。

状态

  • 初状态：
    $all_vis_state = 2^n - 1$。

  • 不打歌的情况下，分数为 $0$。

1
dp[0] = 0;
  • 计算出所有状态对应的时间。
1
2
3
for(int i = 1; i <= all_vis_state; i++) {
    time_[i] = time_[i - lowbit(i)] + need[__builtin_ffs(i) - 1];
}
  • 状态转移方程：

不难发现，对于一个非零 $state$ 来说，可以将它为 $1$ 的其中一位换成 $0$，即可从旧的状态转移来。因为这相当于从原来的状态多打了一首歌。

例如：当 $state=(101)_2$ 时，可以从 $(100)_2$ 和 $(001)_2$ 转移来。

因此，如果一个状态 $i$ 的第 $j$ 位为 $1$，存在：

1
dp[i] = max(dp[i], dp[i ^ (1 << j)] + max(rest[j] - need[j] - time_[i ^ (1 << j)], 0));

其中，i ^ (1 << j) 表示把 $i$ 的第 $j$ 位赋为 $0$ 的旧状态，rest[j] - need[j] - time_[i ^ (1 << j)] 表示在旧状态的情况下，打第 $j$ 首歌的得分。

因为得分不能为负数，所以从计算结果和 $0$ 中选择一个较大的。

  • 末状态：当每一首歌都打了之后的得分。
1
ans = dp[all_vis_state];

对于歌名的处理

我们发现，$dp$ 数组只能处理分数，而不能处理歌名的顺序。

所以，需要一个新的数组 $pre[state]$ 记录状态 $state$ 的最优解是从谁转移来的。

于是，状态转移方程变为以下形式：

1
2
3
4
if(dp[i ^ (1 << j)] + max(rest[j] - need[j] - time_[i ^ (1 << j)], 0) >= dp[i]) {
    dp[i] = dp[i ^ (1 << j)] + max(rest[j] - need[j] - time_[i ^ (1 << j)], 0);
    pre[i] = i ^ (1 << j);
}

同时，打印时采用递归的方法。因为 $pre[state]$ 记录的是从谁来，所以要先递归找到更深的状态，再打印名字。

AC Code

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
// template v9
#include <bits/stdc++.h>
#define NO_ANS cout << "No Answer" << endl, exit(0)
#define lowbit(x) ((x) & (-x))

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 22;

int need[N], rest[N];
int dp[1 << N], time_[1 << N], pre[1 << N];

string name[1 << N];

void print_num(int x) {
    if(!x) return;
    print_num(pre[x]);
    int t = x ^ pre[x];
    cout << name[t] << endl;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int n, m, t;
    cin >> n >> m >> t;
    int total_time = 0;
    for(int i = 0; i < n; i++) {
        cin >> name[1 << i] >> need[i] >> rest[i];
        total_time += need[i];
    }
    if(total_time > t) {
        NO_ANS;
    }
    int all_vis_state = (1 << n) - 1;
    for(int i = 1; i <= all_vis_state; i++) {
        time_[i] = time_[i - lowbit(i)] + need[__builtin_ffs(i) - 1];
    }
    dp[0] = 0;
    for(int i = 1; i <= all_vis_state; i++) {
        for(int j = 0; j <= n; j++) {
            if(i & (1 << j)) {
                if(dp[i ^ (1 << j)] + max(rest[j] - need[j] - time_[i ^ (1 << j)], 0) >= dp[i]) {
                    dp[i] = dp[i ^ (1 << j)] + max(rest[j] - need[j] - time_[i ^ (1 << j)], 0);
                    pre[i] = i ^ (1 << j);
                }
            }
        }
    }
    if(dp[all_vis_state] < m) NO_ANS;
    cout << dp[all_vis_state] << endl;
    print_num(all_vis_state);
    return 0;
}

补充

状态转移方程中的取等

题中说需要字典序最小，而给定的数据已经按字典序排列，那么就可以转化成编号小的先打，编号大的后打。

所以，需要让转移过程中打的那首歌的编号尽可能大，也就是之前打过编号小的。

例如，对于状态 $state=(101)_2$ 的分析如下：

  • 它可以从 $(100)_2$ 和 $(001)_2$ 转移来。
    • 如果选择 $(100)_2$，也就是打第一首歌，此时的顺序为 $3 \rightarrow 1$。
    • 如果选择 $(001)_2$，也就是打第三首歌，此时的顺序为 $1 \rightarrow 3$。
  • 显然，第二种符合要求。
  • 也就是说，需要在转移过程中打大编号的歌。

$\mathrm{lowbit}$

$\mathrm{lowbit}$ 函数可以获得一个数字的二进制表示中，最低位的 $1$ 及其后面的 $0$ 表示的数。

例如：

  • $\mathrm{lowbit}(3)=\mathrm{lowbit}((11)_2)=1$
  • $\mathrm{lowbit}(6)=\mathrm{lowbit}((110)_2)=2$
  • $\mathrm{lowbit}(100)=\mathrm{lowbit}((110\ 0100)_2)=4$

实现方式：$\mathrm{lowbit}(x)=x\ \mathrm{and}(-x)$。

$\mathrm{__builtin_ffs}$

这个函数是内置函数，可以直接使用。

作用为：获取最低位的 $1$ 所在的位置（从 $1$ 开始）。

例如：

  • $\mathrm{__builtin_ffs}(2)=\mathrm{__builtin_ffs((10)_2)}=2$
  • $\mathrm{__builtin_ffs}(3)=\mathrm{__builtin_ffs((11)_2)}=1$
  • $\mathrm{__builtin_ffs}(100)=\mathrm{__builtin_ffs((110\ 0100)_2)}=3$
  • $\mathrm{__builtin_ffs}(1024)=\mathrm{__builtin_ffs((100\ 0000\ 0000)_2)}=11$