题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
Main solution = new Main();
solution.run();
}
public int parse(String str) {
return Integer.parseInt(str);
}
public void run() throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String[] args = in.readLine().split(" ");
int v = parse(args[0]), m = parse(args[1]);
int[][] items = new int[m+1][2];
List<Integer>[] tree = new List[m+1];
for ( int i = 1; i <= m; i++ ) {
String[] info = in.readLine().split(" ");
int price = parse(info[0]), importance = parse(info[1]), master = parse(info[2]);
items[i][0] = price;
items[i][1] = importance*price;
add(tree,master,i);
}
int[][] dp = new int[m+1][v+1];
dfs(items,tree,0,v,dp);
System.out.println(dp[0][v]);
}
public void dfs(int[][] items, List<Integer>[] tree, int cur, int v, int[][] dp) {
int volume = items[cur][0], importance = items[cur][1];
if ( tree[cur] != null ) {
for ( int child : tree[cur] ) {
dfs(items,tree,child,v,dp);
for ( int j = v; j >= 0; j-- ) {
for ( int k = 0; k <= j; k++ ) {
dp[cur][j] = Math.max(dp[cur][j], dp[cur][j - k] + dp[child][k]);
}
}
}
}
for ( int j = v; j >= volume; j-- ) {
dp[cur][j] = dp[cur][j-volume] + importance;
}
for ( int j = volume-1; j >= 0; j-- ) {
dp[cur][j] = 0;
}
}
public void add(List<Integer>[] tree, int parent, int child) {
if ( tree[parent] == null ) {
tree[parent] = new ArrayList<>();
}
tree[parent].add(child);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla