hdu 1078(记忆化搜索)
2024-10-17 03:13:06
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1078
//dp[i][j]表示从点i,j处开始能获得的最多cheese
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std; int n,k,dp[101][101],map[101][101]; int dfs(int a,int b){
if(dp[a][b]) return dp[a][b];
dp[a][b] = map[a][b];
for(int i = 1;i<=k;i++){
if(a+i<n&&map[a+i][b]>map[a][b])
dp[a][b] = max(dp[a][b],dfs(a+i,b)+map[a][b]);
if(a-i>=0&&map[a-i][b]>map[a][b])
dp[a][b] = max(dp[a][b],dfs(a-i,b)+map[a][b]);
if(b-i>=0&&map[a][b-i]>map[a][b])
dp[a][b] = max(dp[a][b],dfs(a,b-i)+map[a][b]);
if(b+i<n&&map[a][b+i]>map[a][b])
dp[a][b] = max(dp[a][b],dfs(a,b+i)+map[a][b]);
}
return dp[a][b];
} int main(void){
while(scanf("%d %d",&n,&k)!=EOF){
if(n==-1&&k==-1) break;
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++)
scanf("%d",&map[i][j]);
}
memset(dp,0,sizeof(dp));
printf("%d\n",dfs(0,0));
}
}
最新文章
- ManagementClass类解析和C#如何获取硬件的相关信息
- PHP的运行机制与原理(底层) [转]
- Windows Store App 过渡动画
- VBS操作剪切板
- Linux系统Shutdown命令定时关机详解
- CreateThread函数&;amp;&;amp;CString::GetBuffer函数
- 19_高级映射:一对多查询(使用resultMap)
- ViewPage 大圣归来 原生示例
- 流Stream个人学习理解
- Linux企业级项目实践之网络爬虫(19)——epoll接口
- iOS国际化和genstrings所有子目录本地化字符串
- Node.js之操作文件系统(一)
- Nginx服务器 配置 https
- mysql c connector 多条sql语句执行示例
- 川普和习G-20会面为缓和中美贸易战提供了很大的机会
- Action访问Servlet API的三种方法
- 秒懂,Java 注解 (Annotation)你可以这样学 - CSDN博客
- Spark内存分配诊断
- 关于 redis、memcache、mongoDB 的对比 转
- .NetCore 利用Jenkins在 Windows平台下打包发布Angular项目