CSP-S 2019 第一轮 第34题：完善程序（第 19 题）第 1 空

题目

1. （匠人的自我修养）

一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。

输入第一行有两个数，分别为新技术个数 $n(l\leq n\leq 10^3)$，以及己有经验值（$\le10^7$）。

接下来 $n$ 行。第 $i$ 行的两个正整数，分别表示学习第 $i$ 个技术所需的最低经验值（$\le10^7$），以及学会第 $i$ 个技术后可获得的经验值（$\leq 10^7$）。

接下来 $n$ 行。第 $i$ 行的第一个数 $m_i$（$0\le m_i<n$），表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数，表示第 $i$ 个技术的相关技术编号。

输出最多能学会的新技术个数。

下面的程序以 $O(n^2)$ 的时间复杂度完成这个问题，试补全程序。

#include<cstdio>
using namespace std;
const int maxn = 1001;

int n;
int cnt[maxn];
int child [maxn][maxn];
int unlock[maxn];
int threshold[maxn], bonus[maxn];
int points;
bool find(){
    int target = -1;
    for (int i = 1; i <= n; ++i)
        if(① && ②){
            target = i;
            break;
    }
    if(target == -1)
        return false;
    unlock[target] = -1;
    ③
    for (int i = 0; i < cnt[target]; ++i)
        ④
    return true;
}

int main(){
    scanf("%d%d", &n, &points);
    for (int i = 1; i <= n; ++i){
        cnt[i] = 0;
        scanf("%d%d", &threshold[i], &bonus[i]);
    }
    for (int i = 1; i <= n; ++i){
        int m;
        scanf("%d", &m);
        ⑤
        for (int j = 0; j < m; ++j){
            int fa;
            scanf("%d", &fa);
            child[fa][cnt[fa]] = i;
            ++cnt[fa];
        }
    }

    int ans = 0;
    while(find())
        ++ans;

    printf("%d\n", ans);
    return 0;
}

①处应填（）

选项

• A. unlock[i] <= 0
• B. unlock[i] >= 0
• C. unlock[i] == 0
• D. unlock[i] == -1

答案

C

题解

应选 C：unlock[i] == 0。

unlock[i] 表示第 i 个技术还有多少个前置技术没有学会：

• 大于 0：前置技术尚未全部学会，不能学习。
• 等于 0：前置技术已全部学会，可以继续检查经验值是否足够。
• 等于 -1：这个技术已经学过，不能重复学习。

因此，选择可学习技术的完整条件是：

``cpp if (unlock[i] == 0 && points >= threshold[i]) ``

注意不能选 A：unlock[i] <= 0 会把已经学过、标记为 -1 的技术再次选中。

这道题的思路是：只要存在能学的技术，就立刻学习它。因为学习会增加经验值、解除其他技术的前置限制，不会妨碍后续学习，所以这样能得到最多的学习数量。