完善程序（1） 1-5题 组合题 （匠人的自我修养）一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。 输入第一行有两个数，分别为新技术个数n（1≤n≤103），以及已有经验值（≤107）。 接下来n行。第i行的两个正整数，分别表示学习第i个技术所需的最低经验值（≤107），以及学会第i个技术后可获得的经验值（≤104）。 接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。 下面的程序已O（n2）的时间复杂完成这个问题，试补全程序。 #inclde using namesoace std； const int maxn = 1001； int n； int cnt [maxn] int child [maxn] [maxn]； int unlock[maxn]; int unlock[maxn]; int threshold [maxn],bonus[maxn]; 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＜cut[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; }
正确答案：完善程序①答案：unlock[i]==0（该技术未解锁且可学）。核心：技术可学判定。
试卷来源：2019 CSP-S提高级（第一轮）C++真题