这道题用python做了很久，系统一直提示超时。因为代码中有一块4层嵌套的循环，python的二维数组似乎效率不太高。昨天晚上睡觉前还是没有做出来，因此想试试用Java能不能行。早上起床就马上开始写Java版的代码，几次就AC了。结论是如果下次碰到有多重循环的情况，python不能胜任的话，可以考虑Java。不过也有可能是因为笔者的python不行。
以下是AC的Java代码：
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
final int MAX_SIZE = 501;
// 先前车队的装备方案
// pre_carry[i][j]表示头盔数为i，盔甲数为j时的长靴数
int[][] pre_carry = new int[MAX_SIZE][MAX_SIZE];
// 先前车队加上当前车队后的装备方案
int[][] current_carry = new int[MAX_SIZE][MAX_SIZE];
// 装备信息
int w1, s1, d1, w2, s2, d2, w3, s3, d3, c1, c2, c3, d4;
Scanner cin = new Scanner(System.in);
int no = 1;
while (true) {
int n = cin.nextInt();
if (n == 0) {
break;
}
// 读入装备信息
w1 = cin.nextInt();
s1 = cin.nextInt();
d1 = cin.nextInt();
w2 = cin.nextInt();
s2 = cin.nextInt();
d2 = cin.nextInt();
w3 = cin.nextInt();
s3 = cin.nextInt();
d3 = cin.nextInt();
c1 = cin.nextInt();
c2 = cin.nextInt();
c3 = cin.nextInt();
d4 = cin.nextInt();
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
pre_carry[i][j] = -1;
}
}
// pre_carry[0][0]为0才可以启动后续的迭代
pre_carry[0][0] = 0;
// 读入n个车队的信息，每读一个车队，更新装备方案
// 最终pre_carry中会存储所有的装备方案
while (n > 0) {
int w = cin.nextInt();
int s = cin.nextInt();
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
current_carry[i][j] = -1;
}
}
// i为头盔数，j为盔甲数，k为长靴数
for (int i = 0; w - i * w1 >= 0 && s - i * s1 >= 0; i++) {
for (int j = 0; w - i * w1 - j * w2 >= 0
&& s - i * s1 - j * s2 >= 0; j++) {
int w_remain = w - i * w1 - j * w2;
int s_remain = s - i * s1 - j * s2;
int k = Math.min(w_remain / w3, s_remain / s3);
// 遍历先前车队的装备方案，将新的装备方案更新到current_carry中
for (int ii = 0; ii < MAX_SIZE; ii++) {
for (int jj = 0; jj < MAX_SIZE; jj++) {
if (pre_carry[ii][jj] == -1) {
break;
}
current_carry[ii + i][jj + j] = Math.max(
current_carry[ii + i][jj + j], k
+ pre_carry[ii][jj]);
}
}
}
}
// 两个数组交换一下
int[][] temp = pre_carry;
pre_carry = current_carry;
current_carry = temp;
n--;
}
// 读完车队信息后，pre_carry中保存所有的装备方案
// 遍历一遍所有的装备方案，计算出最优
int max_defend = 0;
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
if (pre_carry[i][j] >= 0) {
int defend = 0;
if (d4 > c1 * d1 + c2 * d2 + c3 * d3) {
int set_num = Math.min(i / c1,
Math.min(j / c2, pre_carry[i][j] / c3));
defend = set_num * d4;
defend += (i - set_num * c1) * d1
+ (j - set_num * c2) * d2
+ (pre_carry[i][j] - set_num * c3) * d3;
} else {
defend = i * d1 + j * d2 + pre_carry[i][j] * d3;
}
max_defend = Math.max(max_defend, defend);
}
}
}
if (no == 1) {
System.out.print("Case " + no + ": " + max_defend);
} else {
System.out.print("\n\nCase " + no + ": " + max_defend);
}
no++;
}
}
}
