1717: CSP-S19 匠人的自我修养（完善程序）

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

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

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

接下来 n 行。第 i 行的第一个数 m(i)（0≤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;

}

   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