巧用记忆化搜索代替暴力递归(洛谷P1464题题解,Java语言描述)
程序员文章站
2022-07-13 13:53:02
...
题目要求
分析
如果……你信了这题干,真的写了递归……TLE警告!!!
所以,就需要优化嘛……
[−9223372036854775808,9223372036854775807]这个范围,就是C的longlong / Java的long诶,算是一种数很大但还有良心的提示吧。
这题比较适合记忆化搜索,这也是我第一次写记忆化搜索的题解诶,就扯一扯……
一般说来,动态规划总要遍历所有的状态,而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝,可能剪去大量不必要的状态,因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序,但是每求解一个状态,就将它的解保存下来,以后再次遇到这个状态的时候,就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点,因而还是很有实用价值的。
对于本题的话,只要一个记忆化储存就可以避免大量运算量(大佬们都说这玩意和递推/动态规划差不多)。
主要思路就是开一个三维数组,把每一个“w”函数的值储存起来,下一次就可以直接调用,节省大量时间。
使用的时候还要先想,记忆化的数组要开多大。对于这个题来说,输入数据在long(Java)范围内,对于每一组a,b,c都使用一个变量来进行记忆化是不现实的。
但是,根据题意,当a<0 or b<0 or c<0时,返回值都是1,当a>20 or b>20 or c>20时,返回值都是w(20,20,20),因此,对于以上的这些数据,我们可以不进行记忆化处理。
所以, long[25][25][25] 就可以了……
输出注意空格!!!我因此白白WA一次,真悲催啊~~
AC代码(Java语言描述)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static long[][][] array = new long[25][25][25];
private static long w(int a, int b, int c) {
if(a <= 0 || b <= 0 || c <= 0) {
return 1;
}
if(a > 20 || b > 20 || c > 20) {
return w(20, 20, 20);
}
if(a < b && b < c) {
if(array[a][b][c-1] == 0) {
array[a][b][c-1] = w(a, b, c-1);
}
if(array[a][b-1][c-1] == 0) {
array[a][b-1][c-1] = w(a, b-1 ,c-1);
}
if(array[a][b-1][c] == 0) {
array[a][b-1][c] = w(a, b-1, c);
}
array[a][b][c] = array[a][b][c-1] + array[a][b-1][c-1] - array[a][b-1][c];
} else {
if(array[a-1][b][c] == 0) {
array[a-1][b][c] = w(a-1, b, c);
}
if(array[a-1][b-1][c] == 0) {
array[a-1][b-1][c] = w(a-1, b-1 ,c);
}
if(array[a-1][b][c-1] == 0) {
array[a-1][b][c-1] = w(a-1, b, c-1);
}
if(array[a-1][b-1][c-1] == 0) {
array[a-1][b-1][c-1] = w(a-1, b-1, c-1);
}
array[a][b][c] = array[a-1][b][c] + array[a-1][b][c-1] + array[a-1][b-1][c] - array[a-1][b-1][c-1];
}
return array[a][b][c];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String endFlag = "-1 -1 -1";
List<StringBuilder> list = new ArrayList<>();
while (true) {
String temp = scanner.nextLine();
if (endFlag.equals(temp)) {
break;
}
StringBuilder builder = new StringBuilder();
String[] nums = temp.split("\\s+");
int a = Integer.parseInt(nums[0]), b = Integer.parseInt(nums[1]), c = Integer.parseInt(nums[2]);
builder.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(w(a,b,c));
list.add(builder);
}
scanner.close();
for (StringBuilder s : list) {
System.out.println(s);
}
}
}