编号：ALGO-19 题目：方格取数 关键字：动态规划 类型：vip试题 问题描述：
设有N*N的方格图(N<=10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 输入格式
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。 输出格式
只需输出一个整数，表示2条路径上取得的最大的和。 样例输入 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 样例输出
67 参考代码：
import class Main{ static int x; static int y; static int n;
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader); n = ());
int[][] tag = new int[2 * n + 1][2 * n + 1]; int[][] arr = new int[n * n][2]; out: for (int i = 1; ; i++) { String[] str = ().split(\ for (int j = 0; j < 1; j++) { x = arr[i][0] = (str[0]); y = arr[i][1] = (str[1]); tag[x][y] = (str[2]);
if (x == 0 && y == 0 && tag[x][y] == 0){ dp(tag); break out; } } } }
public static void dp(int[][] tag) { int[][] temp = new int[2 * n][2 * n]; int k;
for (int i = 2; i <= 2 * n; i++) {
for (int t = min(i, n), j = t; j > 0; j--) { for (k = t; k > 0; k--) {
temp[j][k] = max(temp[j][k], temp[j - 1][k - 1]); temp[j][k] = max(temp[j][k], temp[j - 1][k]); temp[j][k] = max(temp[j][k], temp[j][k - 1]); if (j == k)
temp[j][k] += tag[j][i - j]; else
temp[j][k] += tag[j][i - j] + tag[k][i - k]; } } } }
public static int max(int a, int b) { return a > b a : b; }
public static int min(int a, int b) { return a > b b : a; } }
编号：ALGO-20 题目：求先序排列 关键字：递归 类型：vip试题 问题描述：
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。 输入格式
两行，每行一个字符串，分别表示中序和后序排列 输出格式
一个字符串，表示所求先序排列
样例输入 BADC BDCA 样例输出 ABCD 参考代码：
import class Main { public static void main(String[] args) {
Scanner scanner = new Scanner;
while ()) { String str1 = ();
String str2 = ();
showResult(str1, str2);
}
}
private static void showResult(String str1, String str2) { char chl = () - 1);
int index = (chl);
}
编号：ALGO-21 题目：装箱问题 关键字：动态规划 类型：vip试题 问题描述：
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入格式
第一行为一个整数，表示箱子容量； 第二行为一个整数，表示有n个物品；
接下来n行，每行一个整数表示这n个物品的各自体积。 输出格式
一个整数，表示箱子剩余空间。 样例输入
}
if (index < () - 1) { }
showResult(index + 1),
(index, () - 1));
if (index > 0) { }
showResult(0, index), (0, index));