dp[i][j]，表示有 i 个骰子，掷出点数范围为[j…6j]的每个点数的掷法，那么对于dp[1]，所有点数都只有一种方法。
当n=2时，如果要掷出点数3，组合方式=1 + 2 / 2 + 1，就两种，我们假设现在已经掷了一个骰子，点数为k，那么我们还需要去看另外一个骰子的情况，因为要让点数凑成3，所以就看dp[i - 1][3 - k]，就是说看一个骰子掷出3-k点数的种类数。
也就是说，站在最后一个骰子的角度去考虑问题，考虑前面的骰子能够为这个骰子带来什么？
class Solution {
public int[] numberOfDice(int n) {
// ans[i][j] i个骰子，掷出j个点的每个点的方案数
int[][] ans = new int[n + 1][6 * n + 1];
// 一个骰子掷出1-6点数的种类都=1
for (int i = 1; i <= 6; i++) {
ans[1][i] = 1;
}
// 遍历n个骰子
for (int i = 2; i <= n; i++) {
// 遍历n个骰子的点数总和的范围
for (int j = i; j <= i * 6; j++) {
// 当前这个骰子投掷的点数大小
for (int k = 1; k <= 6; k++) {
if (j - k > 0) {
// 当前这个骰子点数为k，那么前面i-1个骰子的点数之和只能为j - k
ans[i][j] += ans[i - 1][j - k];
}
}
}
}
return Arrays.copyOfRange(ans[n], n, 6 * n + 1);
}
}
站在当前地窖考虑，考虑前面有几个地窖能到达当前地窖，所以可以很容易得到dp数组的含义，dp[i]，以第i个地窖结束的路径，挖得最多的地雷数，这个地雷数只是以第i个地窖结束的路径的最大值，并不是全局的，所以还要记录一个全局最大值，最后利用这个全局最大值，从尾到头依次遍历，寻找出路径。
需要注意的是，对于所有dp[i]的初始值，所有地窖都可以只考虑自己，所以初始值就是当前地窖的地雷数。
import java.util.*;
import java.io.*;
public class Main {
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] bomb = new int[n + 1];
for (int i = 0; i < n; i++) {
bomb[i + 1] = scan.nextInt();
}
boolean[][] vis = new boolean[n + 1][n + 1];
while (true) {
int x = scan.nextInt();
int y = scan.nextInt();
if (x == 0 && y == 0) break;
vis[x][y] = true;
}
// dp[i]，挖的最后一个地窖为i时，能够挖到的最大地雷数
int[] dp = new int[n + 1];
// dp[i]中每一个元素，只考虑自身地窖时，最大地雷数=bomb[i]
for (int i = 1; i <= n; i++) {
dp[i] = bomb[i];
}
int max = dp[1];
// 遍历结束位置
for (int i = 2; i <= n; i++) {
// 可能的开始位置
for (int j = 1; j < i; j++) {
if (vis[j][i]) {
// j -> i 有通路
dp[i] = Math.max(dp[i], dp[j] + bomb[i]);
}
}
// 记录全局最大值
max = Math.max(max, dp[i]);
}
StringBuilder sb = new StringBuilder();
int tmp = max;
// 从后往前记录路径
for (int i = n; i >= 1; i--) {
if (dp[i] == tmp) {
tmp -= bomb[i];
if (tmp == 0) {
sb.insert(0, i);
} else {
sb.insert(0, "-" + i);
}
}
}
System.out.println(sb.toString());
System.out.println(max);
}
}
首先需要知道的是，直接走和使用技能哪个更快：
我们可以先算出来只使用技能的情况下，1-t秒的每一秒能走多远。但是这样考虑问题是不够全面的，当剩余距离很小时，就不需要再等技能恢复，直接跑就行，所以对于每一秒，我们还需要将：使用技能的距离 与 直接跑的距离 作比较，取其中的最大值作为最终的最大距离。
import java.util.*;
import java.io.*;
public class Main {
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] input = reader.readLine().trim().split(" ");
int M = Integer.parseInt(input[0]);
int S = Integer.parseInt(input[1]);
int T = Integer.parseInt(input[2]);
// dp[i], 第 is 能够到达的最远距离
int[] dp = new int[T + 1];
// 先求得只使用技能的每秒能够到达的最远距离
for (int i = 1; i <= T; i++) {
if (M >= 10) {
// 魔力值允许释放技能就立马释放
M -= 10;
dp[i] = dp[i - 1] + 60;
} else {
// 魔力值不够释放技能，就原地等待
M += 4;
dp[i] = dp[i - 1];
}
}
// 再求得穿插使用直接跑的情况下，每秒能够到达的最远距离
for (int i = 1; i <= T; i++) {
dp[i] = Math.max(dp[i], dp[i - 1] + 17);
}
// 两步处理完后得到的就是每一秒能够到达的最远距离
boolean flag = false;
for (int i = 1; i <= T; i++) {
if (dp[i] >= S) {
flag = true;
System.out.println("Yes");
System.out.println(i);
break;
}
}
if (!flag) {
// 逃离不了就输出能够走的最远距离
System.out.println("No");
System.out.println(dp[T]);
}
}
}
是最长公共子序列的样子，但是需要输出可能方案情况，这就不好办了。
import java.util.*;
import java.io.*;
public class Main {
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static String a, b;
static int[][] dp;
static int n1, n2;
static int[][] lst1;
static int[][] lst2;
// 存储最后可能路径
static List<String> list = new LinkedList<>();
public static void main(String[] args) throws IOException {
a = reader.readLine().trim();
b = reader.readLine().trim();
// dp[i][j]
// a[1...i] 与 b[1...j] 的 LCS
n1 = a.length();
n2 = b.length();
// lst[i][j]，记录串中前i个字符中，第j个字母(0-25号字母)最后一次出现的位置
lst1 = new int[n1 + 1][30];
lst2 = new int[n2 + 1][30];
for (int i = 1; i <= n1; i++) {
for (int j = 0; j < 26; j++) {
if (a.charAt(i - 1) == (j + 'a')) {
lst1[i][j] = i;
} else {
// 如果不相等，只能看前i-1个字符
lst1[i][j] = lst1[i - 1][j];
}
}
}
for (int i = 1; i <= n2; i++) {
for (int j = 0; j < 26; j++) {
if (b.charAt(i - 1) == (j + 'a')) {
lst2[i][j] = i;
} else {
lst2[i][j] = lst2[i - 1][j];
}
}
}
dp = new int[n1 + 1][n2 + 1];
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
dfs(n1, n2, new StringBuilder());
// 升序输出所有结果（排序 + 去重）
Collections.sort(list);
for (int i = 0; i < list.size(); i++) {
if (i > 0 && list.get(i - 1).equals(list.get(i))) continue;
System.out.println(list.get(i));
}
}
static void dfs(int n, int m, StringBuilder sb) {
if (dp[n][m] + sb.length() < dp[n1][n2]) return;
// 遍历完，存入最终结果
if (n == 0 || m == 0) {
list.add(sb.toString());
return;
}
// 最后一个字符相同时才考虑下一个字符
if (dp[n - 1][m - 1] + 1 == dp[n][m] && a.charAt(n - 1) == b.charAt(m - 1)) {
dfs(n - 1, m - 1, new StringBuilder(sb).insert(0, a.charAt(n - 1)));
} else {
// 26个字母，暴力枚举两个串中最后一个可能相同的字符
// dfs函数中的第一行就对不满足题意的情况进行了剪枝
for (int i = 0; i < 26; i++) {
int tx = lst1[n][i];
int ty = lst2[m][i];
dfs(tx, ty, sb);
}
}
}
}
公共序列的感觉，但是由于要去取出k个互不重叠的非空子串（一个字符也算子串），来拼接出新的子串，这就很…。
题解都没看懂，g
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）