洛谷 P1544 三倍经验【记忆化搜索】

大家好，我是讯享网，很高兴认识大家。

三倍经验

传送门：P1544 三倍经验

题目描述

数字金字塔由 $n$ 行整数组成，第 $i(1\le i\le n)$ 行有 $i$ 个数字，一个示例如下。

 7 3 9 8 1 0 2 7 4 4 4 5 2 6 5

讯享网

现在你在金字塔的顶部（第一行），你希望走到金字塔的底部（第 $n$ 行），每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友，你可以选择金字塔中的不多于 $k$ 个数字让他们成为原来的 $3$ 倍。

你会收集你路上经过的所有位置上的数字，最后的得分即为收集的数字之和，求最大得分。

输入格式

第一行输入两个整数 $n, k$ ，表示数字金字塔的行数和乘 $3$ 的数字个数最大值；
接下来 $n$ 行，其中的第 $i$ 行有 $i$ 个以空格隔开的整数依次表示数字金字塔第 $i$ 行的数字 $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$ 。

输出格式

一行一个整数，表示最大得分。

样例 #1

样例输入 #1

讯享网5 3 7 3 9 8 1 0 2 7 4 4 4 5 2 6 5

样例输出 #1

提示

对于 $30\%$ 的数据，满足 $k\le n\le 6$ ，并且对于任意 $1\le i\le n$ ， $1\le j\le i$ 满足 $0\le a_{i,j}\le 100$ ；
对于 $100\%$ 的数据，满足 $1\le n\le100$ ， $0\le k\le \dfrac{n(n+1)}{2}$ ，且对于任意 $1\le i\le n$ ， $1\le j\le i$ 满足 $|a_{i,j}|\le 10^9$ 。

解题思路

这道题目可以使用记忆化搜索和动态规划求解，本文给出记忆化搜索解法：

讯享网

定义一个二维数组a存放数字金字塔，一个三维计数数组cnt 统计经过路径数字总值。使用mark三维数组进行是否遍历过的标记。

初始化cnt中的每个值为最小值（避免判断最小值时出错），从最顶部数开始搜索。

若超出范围，返回0

若已经搜索过，则直接返回值。

如果还有修改次数，则还可进行修改，依次选择左边或者右边的数（分类讨论，取最大值）；次数用尽则不能再修改。

再写出不修改的情况，分类讨论，取最大值，标记已访问，返回结果。

解题代码：

讯享网import java.io.*; import java.util.Arrays; public class Main { 
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static int n,k; static long ans; static long [][] a = new long[105][105]; static long [][][] cnt = new long[105][105][105]; static long [][][] mark = new long[105][105][105]; public static void main(String[] args) throws IOException { 
    n = nextInt(); k = nextInt(); if(k>n)k = n; for (int i = 1; i <=n ; i++) { 
    for (int j = 1; j <=i ; j++) { 
    a[i][j] = nextLong(); } } //初始化 for(long[][] k:cnt){ 
    for(long[] t:k){ 
    Arrays.fill(t,Long.MIN_VALUE); } } ans = dfs(1,1,0); out.println(ans); out.flush(); } public static long dfs(int x,int y,int p){ 
    if(x<1 || x>n || y<1 || y>n) return 0;//越界 if(mark[x][y][p]==1){ 
    return cnt[x][y][p]; } if(p<k){ 
   //还有修改次数 cnt[x][y][p] = Math.max(cnt[x][y][p],dfs(x+1,y,p+1)+a[x][y]*3L);//选左边 cnt[x][y][p] = Math.max(cnt[x][y][p],dfs(x+1,y+1,p+1)+a[x][y]*3L);//选右边 } //分类讨论 cnt[x][y][p] = Math.max(cnt[x][y][p],dfs(x+1,y,p)+a[x][y]);//没修改 cnt[x][y][p] = Math.max(cnt[x][y][p],dfs(x+1,y+1,p)+a[x][y]); mark[x][y][p] = 1;//已访问 return cnt[x][y][p]; } public static int nextInt() throws IOException{ 
    in.nextToken(); return (int)in.nval; } public static long nextLong() throws IOException{ 
    in.nextToken(); return (long)in.nval; } }

如果本文对你有帮助，可以点个赞噢！

洛谷 P1544 三倍经验 【记忆化搜索】