题解 | #购物单#
购物单
https://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
import java.io.*;
import java.util.*;
import java.lang.Math;
public class Main {
public static void main(String[]args) throws IOException {
Scanner in = new Scanner(System.in);
int money = in.nextInt();
int count = in.nextInt();
int[] v = new int[count + 1];
int[] p = new int[count + 1];
int[] q = new int[count + 1];
int[] f1 = new int[count + 1];
int[] f2 = new int[count + 1];
boolean flag = true;
int dw = 100;
// 数据录入
if (money == 0 || count == 0) {
System.out.println(0);
return;
}
for (int i = 1 ; i < count + 1; i++) {
v[i] = in.nextInt();
if (flag && v[i] % dw != 0) {
dw = 10;
flag = false;
for (int m = 1 ; m < i ; m++) {
p[m] *= 10;
v[m] *= 10;
}
}
v[i] = v[i] / dw;
p[i] = in.nextInt() * v[i];
q[i] = in.nextInt();
if (q[i] > 0) {
if (f1[q[i]] == 0) {
f1[q[i]] = i;
} else {
f2[q[i]] = i;
}
}
}
// 处理数据
money /= dw;
int[][] dp = new int[count + 1][money + 1];
for (int i = 1 ; i < count + 1 ; i++) {
int p1 = 0, p2 = 0, p3 = 0;
int v1 = -1, v2 = -1, v3 = -1;
if (f1[i] != 0) {
v1 = v[i] + v[f1[i]];
p1 = p[i] + p[f1[i]];
}
if (f2[i] != 0) {
v2 = v[i] + v[f2[i]];
p2 = p[i] + p[f2[i]];
}
if (f1[i] != 0 && f2[i] != 0) {
v3 = v1 + v2 - v[i];
p3 = p1 + p2 - p[i];
}
for (int j = 1 ; j < money + 1 ; j ++) {
dp[i][j] = dp[i - 1][j];
if (q[i] == 0) {
if (j >= v[i]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + p[i]);
}
if (v1 != -1 && j >= v1) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v1] + p1);
}
if (v2 != -1 && j >= v2) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v2] + p2);
}
if (v3 != -1 && j >= v3) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v3] + p3);
}
}
}
}
System.out.println(dp[count][money] * dw);
}
}
