不是VIP会员,不能显示答案

题目解答

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

输入第一行有两个数,分别为新技术个数n (l<=n<=10^3)n(l<=n<=10^3),以及己有经验值(<=10^7 )。



接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值(<=10^7),以及学会第i个技术后可获得的经验值(<=10^4)。



接下来n行。第i行的第一个数mi (0<= mi< n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号。

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

下面的程序以(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;
}


选择题

1) ①处应填()

A.unlock[i] <= 0
B.unlock[i] >= 0
C.unlock[i] == 0
D.unlock[i] == -1
2) ②处应填()

A.threshold[i] > points
B.threshold[i] >= points
C.points > threshold[i]
D.points >= threshold[i]
3) ③处应填()

A. target = -1
B.--cnt[target]
C.bonus[target] = 0
D.points += bonus[target]
4) ④处应填()

A. cnt[child[target][i]] -= 1
B.cnt[child[target][i]] = 0
C.unlock[child[target][i]] -= 1
D.unlock[child[target][i]] = 0
5) ⑤处应填()
A. unlock[i] = cnt[i]
B.unlock[i] = m
C.unlock[i] = 0
D.unlock[i] = -1
考点:
分析:
解答:
评论:
老师: