树形DP
没有上司的舞会
Ural大学有 $N$ 名职员，编号为 $1~N$。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 $H_i$ 给出，其中 $1≤i≤N$。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。
输入格式
第一行一个整数N。
接下来$N$ 行，第 $i$ 行表示 $i$ 号职员的快乐指数$H_i$。
接下来 $N-1$ 行，每行输入一对整数 $L, K$, 表示 $K$ 是 $L$ 的直接上司。
输出格式
输出最大的快乐指数。
数据范围
$1≤N≤6000$
$−128≤Hi≤127$输入样例
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5输出样例
5
public class Prom {
final static int N = 6010;
static int idx = 0;
final static int[][] f = new int[N][2];
final static int[] e = new int[N], ne = new int[N], h = new int[N], happy = new int[N];
final static boolean[] hasFather = new boolean[N];
private static void add(int a, int b) {
e[idx] = a;
ne[idx] = h[b];
h[b] = idx++;
}
private static void dfs(int u) {
f[u][1] = happy[u];
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
dfs(j);
f[u][0] += Math.max(f[j][0], f[j][1]);
f[u][1] += f[j][0];
}
}
public static void main(String[] args) {
int n = Tools.getInt();
for (int i = 1; i <= n; i++) happy[i] = Tools.getInt();
Arrays.fill(h, -1);
for (int i = 0; i < n - 1; i++) {
int a = Tools.getInt(), b = Tools.getInt();
add(a, b);
hasFather[a] = true;
}
int root = 1;
while (hasFather[root]) root++;
dfs(root);
System.out.println(Math.max(f[root][0], f[root][1]));
}
}
记忆化搜索
滑雪
给定一个$R$ 行 $C$ 列的矩阵，表示一个矩形网格滑雪场。
矩阵中第 $i$ 行第 $j$ 列的点表示滑雪场的第 $i$ 行第 $j$ 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9在给定矩阵中，一条可行的滑行轨迹为24-17-2-1。
在给定矩阵中，最长的滑行轨迹为25-24-23-…-3-2-1，沿途共经过25个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 $R$ 和 $C$。
接下来 $R$ 行，每行包含 $C$ 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
$1≤R,C≤300$
$0≤矩阵中整数≤10000$输入样例
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9输出样例
25
public class Skating {
final static int N = 310;
final static int[][] f = new int[N][N], h = new int[N][N];
final static int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
private static int dp(int x, int y, int n, int m) {
if (h[x][y] != -1) return h[x][y];
h[x][y] = 1;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 1 && a <= n && b >= 1 && b <= m && f[x][y] > f[a][b])
h[x][y] = Math.max(h[x][y], dp(a, b, n, m) + 1);
}
return h[x][y];
}
public static void main(String[] args) {
int n = Tools.getInt(), m = Tools.getInt();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = Tools.getInt();
for (var a : h) Arrays.fill(a, -1);
int ret = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ret = Math.max(ret, dp(i, j, n, m));
System.out.println(ret);
}
}
参考
