欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

巧用记忆化搜索代替暴力递归(洛谷P1464题题解,Java语言描述)

程序员文章站 2022-07-13 13:53:02
...

题目要求

P1464题目链接

巧用记忆化搜索代替暴力递归(洛谷P1464题题解,Java语言描述)
巧用记忆化搜索代替暴力递归(洛谷P1464题题解,Java语言描述)

分析

如果……你信了这题干,真的写了递归……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);
        }
    }

}