HDU 1078 FatMouse and Cheese

一时失言乱红尘 2022-04-13 03:18 185阅读 0赞

## 原题目链接：[HDU1078][] ##

--------------------

## 分类 ##

HDU 动态规划 dfs 记忆化搜索

--------------------

## 题意 ##

题意就是在n的方阵中，从最左上角，每次横向或纵向最多走k步，每走一步都要求下一步的数字比上一步的数字更大，从起点开始走到一处求和求到一处，求出最大的和。

--------------------

## 样例输入输出 ##

Sample Input

3 1
    1 2 5
    10 11 6
    12 12 7
    -1 -1

Sample Output

37

--------------------

## 想法 ##

记忆化搜索，每次最多走k步，看代码

--------------------

## 代码 ##

156ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/26 */
     /* dfs + dp 记忆化搜索 */
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 111;
    int a[maxn][maxn];
    int dp[maxn][maxn];
    int n, k; 
    int xx[4] = { 0, 1, 0, -1};
    int yy[4] = { 1, 0, -1, 0};
    int dfs(int x, int y){ 
    	if(!dp[x][y]){ 
    		int ans = 0;
    		for(int i = 1; i <= k; i++){ 
    			
    			for(int j=0;j < 4;j++){ 
    				int x1 = x + i*xx[j];
    				int y1 = y + i*yy[j];
    				if(x1>=0 && x1 < n && y1 >=0 && y1 <n && a[x1][y1] > a[x][y]){ 
    					ans = max(ans, dfs(x1, y1));
    				}
    			}
    		}
    		dp[x][y] = ans  + a[x][y];
    	}
    	return dp[x][y];
    }
    int main()
    { 
    	while(cin >> n >> k){ 
    		if(n == -1 && k == -1){ 
    			break;
    		}
    		for(int i = 0;i < n;i++){ 
    			for(int j = 0;j < n;j++){ 
    				cin >> a[i][j];
    			}
    		}
    		memset(dp,0,sizeof(dp));
    		cout << dfs(0, 0) << endl;
    	}
        return 0;
    }

--------------------

[HDU1078]: http://acm.hdu.edu.cn/showproblem.php?pid=1078

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 1009 FatMouse' Trade

FatMouse' Trade Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

灰太狼/ 2022年06月16日 12:54/ 0 赞/ 213 阅读

相关 ACM 记忆化搜索 Function Run Fun & FatMouse and Cheese

滴，集训第四天打卡。今天是记忆化搜索和字典树... 记忆话搜索可以举一反三..字典树看了一下午几乎是绝望的.. 所以下一篇会是字典树专题... POJ 1579 Fu

ゝ一纸荒年。/ 2022年06月12日 09:36/ 0 赞/ 198 阅读

相关 P - FatMouse and Cheese HDU - 1078——dfs+记忆化搜索

Think: 1知识点：dfs+记忆化搜索 2题意：输入一个邻接矩阵，求一条递增路径，满足沿四个方向直线移动最多k步的条件，使得路径经过的点权之和最大 [vjudge

柔情只为你懂/ 2022年06月10日 03:59/ 0 赞/ 199 阅读

相关 HDU-FatMouse' Trade （贪心）

FatMouse' Trade Problem Description FatMouse prepared M pounds of cat food,

心已赠人/ 2022年05月26日 04:22/ 0 赞/ 200 阅读

相关 FatMouse and Cheese ————记忆化搜索

FatMouse has stored some cheese in a city. The city can be considered as a square grid o

灰太狼/ 2022年05月17日 11:08/ 0 赞/ 168 阅读

相关【1009 HDU】FatMouse' Trade

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1009][http_acm.hdu.edu.cn_showproblem.ph

痛定思痛。/ 2022年05月13日 06:18/ 0 赞/ 241 阅读

相关 HDU 1009 FatMouse' Trade

原题目链接[HDU1009][] -------------------- 分类 HDU 贪心 -------------------- 题意贪心专题

末蓝、/ 2022年04月16日 04:59/ 0 赞/ 217 阅读

相关 HDU 1078 FatMouse and Cheese

原题目链接：[HDU1078][] -------------------- 分类 HDU 动态规划 dfs 记忆化搜索 -------------------

一时失言乱红尘/ 2022年04月13日 03:18/ 0 赞/ 186 阅读

相关 HDU-1009——FatMouse' Trade

[ FatMouse' Trade][FatMouse_ Trade] Problem D

「爱情、让人受尽委屈。」/ 2022年04月11日 09:54/ 0 赞/ 213 阅读

相关 HDU 1078 FatMouse and Cheese（记忆化搜索，DP）

目录 1.题目 2.题意 3.思路 4.代码 1.题目 Fa

╰+哭是因爲堅強的太久メ/ 2021年08月29日 00:50/ 0 赞/ 358 阅读