(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的 经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的 值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个 新技术。
输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤10^7). 接下来n行。第i行的两个整数,分别表示学习第i个技术所需的最低经验值(≤10^7),以及学会第i个技 术后可获得的经验值(≤10^4)。 接下来n行。第i行的第一个数mi(0≤mi<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 points; 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 < 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处应填( )
unlock[i]<=0
unlock[i]>=0
unlock[i]==0
unlock[i]==-1
②处应填( )
threshold[i]>points
threshold[i]>=points
points>threshold[i]
points>=threshold[i]
③处应填( )
target = -1
- -cnt[target]
bbonus[target]
points += bonus[target]
④处应填( )
cnt [child[target][i]] -=1
cnt [child[target][i]] =0
unlock[child[target][i]] -= 1
unlock[child[target][i]] =0
⑤处应填( )
unlock[i] = cnt[i]
unlock[i] =m
unlock[i] = 0
unlock[i] =-1