我写了个思路，不知道对不，有没有大佬讨论讨论
CC直播的运营部门组织了很多运行活动，每个活动需要花费一定的时间参与，主播每参加一个活动即可得到一定的奖励，参与活动可以从任意活动开始，
* 但一旦开始，就需要将后续活动参加完毕（注意，最后一个活动必须参与），活动之间存在一定的依赖关系（不存在环的情况），现在给出所有的活动时间与依赖关系，
* 以及给出有限的时间，请帮主播计算在有限的时间内，可以获得的最大奖励以及需要的最少时长。
*
* 活动 | 活动所需时间（天） | 获得奖励（C）
* A 3 2000
* B 3 4000
* C 2 2500
* D 1 1600
* E 4 3800
* F 2 2600
* G 4 4000
* H 3 3500
*
* 如上图所示，给定有限时间为10天，可以获得的最大奖励为11700，需要的时长为9天，参加的活动为BDFH四个
* 输入描述：
* 第一行输入数据N与D，表示有N项活动，D表示给予的时长，0<N<=1000, 0 < D <= 10000,
* 从第二行开始到N+1行，每行描述一个活动的信息，其中第一项表示当前活动需要花费多少时间，
* 第二项表示可以获得的奖励a，之后有N项数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖，每项使用空格分开。
*
* 输出描述：
* 输出两项数据A与T， 用空格分开，A表示所获得的最大奖励，T表示所需要的时长。
*
* 输入：
* 8 10
* 3 2000 0 1 1 0 0 0 0 0
* 3 4000 0 0 0 1 1 0 0 0
* 2 2500 0 0 0 1 0 0 0 0
* 1 1600 0 0 0 0 1 1 1 0
* 4 3800 0 0 0 0 0 0 0 1
* 2 2600 0 0 0 0 0 0 0 1
* 4 4000 0 0 0 0 0 0 0 1
* 3 3500 0 0 0 0 0 0 0 0
* 输出
#算法题##ACM话题#
* 但一旦开始，就需要将后续活动参加完毕（注意，最后一个活动必须参与），活动之间存在一定的依赖关系（不存在环的情况），现在给出所有的活动时间与依赖关系，
* 以及给出有限的时间，请帮主播计算在有限的时间内，可以获得的最大奖励以及需要的最少时长。
*
* 活动 | 活动所需时间（天） | 获得奖励（C）
* A 3 2000
* B 3 4000
* C 2 2500
* D 1 1600
* E 4 3800
* F 2 2600
* G 4 4000
* H 3 3500
*
* 如上图所示，给定有限时间为10天，可以获得的最大奖励为11700，需要的时长为9天，参加的活动为BDFH四个
* 输入描述：
* 第一行输入数据N与D，表示有N项活动，D表示给予的时长，0<N<=1000, 0 < D <= 10000,
* 从第二行开始到N+1行，每行描述一个活动的信息，其中第一项表示当前活动需要花费多少时间，
* 第二项表示可以获得的奖励a，之后有N项数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖，每项使用空格分开。
*
* 输出描述：
* 输出两项数据A与T， 用空格分开，A表示所获得的最大奖励，T表示所需要的时长。
*
* 输入：
* 8 10
* 3 2000 0 1 1 0 0 0 0 0
* 3 4000 0 0 0 1 1 0 0 0
* 2 2500 0 0 0 1 0 0 0 0
* 1 1600 0 0 0 0 1 1 1 0
* 4 3800 0 0 0 0 0 0 0 1
* 2 2600 0 0 0 0 0 0 0 1
* 4 4000 0 0 0 0 0 0 0 1
* 3 3500 0 0 0 0 0 0 0 0
* 输出
* 11700 9
public class OnlineShow {
static int[] max = new int[2];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] graph = new int[n][n + 2];
Map<Integer,Node> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n + 2; j++) {
graph[i][j] = sc.nextInt();
}
Node node = new Node();
node.days = graph[i][0];
node.price = graph[i][1];
map.put(i,node);
}
for (int i = n+1; i >1 ; i--) {
Node node = map.get(i-2);
for (int j = i-2; j >= 0; j--) {
if (graph[j][i] == 1) {
node.list.add(map.get(j));
}
}
}
dfs(map.get(n - 1), m-map.get(n-1).days,map.get(n-1).price);
System.out.print(max[0]+" ");
System.out.print(m-max[1]);
}
private static void dfs(Node node, int m,int money) {
if (node.list.size()==0&&money>max[0]) {
max[0] = money;
max[1]=m;
}
for (int i = 0; i < node.list.size(); i++) {
Node temp = node.list.get(i);
if (m >= temp.days) {
dfs(temp, m - temp.days, money + temp.price);
} else {
if (money > max[0]) {
max[0]=money;
max[1] = m;
}
}
}
}
}
class Node{
int days;
int price;
List<Node> list = new ArrayList<>();
} 
查看25道真题和解析
百度成长空间 412人发布