Login
Accessing this course requires a login. Please enter your credentials below!
一个匠人决定要学习 n 个新技术。要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。
输入第一行有两个数，分别为新技术个数 n(l≤n≤103),以及己有经验值（≤107）。
接下来 n 行。第 i 行的两个正整数，分别表示学习第 i 个技术所需的最低经验值（≤107）,以及学会第i个技术后可获得的经验值（≤107)
接下来 n 行。第 i 行的第一个数 mi（0≤mi<n），表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数，表示第 ii 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 O(n2) 的时间复杂度完成这个问题，试补全程序。
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 | #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; } |
①处应填（）
2、②处应填（）
3、③处应填（）
4、④处应填（）
5、⑤处应填（）
