百度之星2014资格赛 1004 - Labyrinth
2024-08-24 10:44:23
先上题目:
Labyrinth
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2911 Accepted Submission(s): 1007
Problem Description
度度熊是一只喜欢探险的熊,一次偶然落进了一个m*n矩阵的迷宫,该迷宫只能从矩阵左上角第一个方格开始走,只有走到右上角的第一个格子才算走出迷宫,每一次只能走一格,且只能向上向下向右走以前没有走过的格子,每一个格子中都有一些金币(或正或负,有可能遇到强盗拦路抢劫,度度熊身上金币可以为负,需要给强盗写欠条),度度熊刚开始时身上金币数为0,问度度熊走出迷宫时候身上最多有多少金币?
Input
输入的第一行是一个整数T(T < 200),表示共有T组数据。
每组数据的第一行输入两个正整数m,n(m<=100,n<=100)。接下来的m行,每行n个整数,分别代表相应格子中能得到金币的数量,每个整数都大于等于-100且小于等于100。
每组数据的第一行输入两个正整数m,n(m<=100,n<=100)。接下来的m行,每行n个整数,分别代表相应格子中能得到金币的数量,每个整数都大于等于-100且小于等于100。
Output
对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。
每组测试数据输出一行,输出一个整数,代表根据最优的打法,你走到右上角时可以获得的最大金币数目。
每组测试数据输出一行,输出一个整数,代表根据最优的打法,你走到右上角时可以获得的最大金币数目。
Sample Input
2
3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90
2 2
1 1
1 1
Sample Output
Case #1:
18
18
Case #2:
4
4
中文题意不解释,思路:DP,有点像数塔,就是转移的时候需要做的步骤多了一点。在每一次转移去下一层之前需要确定当前一层的每一格三个值,①从上面一层转移到这一个的最大值,②从当前格左边转移过来的最大值,③从当前格右边转移过来的最大值。
分析可知,从当前格左边转移到当前格只于当前格左边的格子有关,从当前格右边转移到当前格只于当前格右边的格子有关。从上一层对应格转移到当前格只于上一层对应的那一格有关。需要注意的是在边界上面的格需要特殊处理,顶层的格(既开始的时候所在那一层)只可以向水平的一个方向和向下转移。而两边的格无法从它的边缘转移到最值,所以最左边的格子的从左边转移过来的最值可以等于从上方转移过来的最值,同理最右边的格子的从右边转移过来的最值可以等于从上方转移过来的最值。(这里定义起点所在那一层是顶层,终点所在那一层是底层)。
上代码:
#include <cstdio>
#include <cstring>
#define max(x,y) (x >= y ? x : y)
#define MAX 102
#define INF (1<<30)
using namespace std; int c[MAX][MAX];
int dp[MAX][MAX]; /* 0 :left 1:behind 2 : right*/
int ldp[MAX][MAX],rdp[MAX][MAX];
int n,m; void reset(){
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) for(int j=;j<=m;j++) dp[i][j] = dp[i][j] = dp[i][j] = -INF;
} int main()
{
int t;
//freopen("data.txt","r",stdin);
scanf("%d",&t);
for(int z=;z<=t;z++){
scanf("%d %d",&m,&n);
memset(c,,sizeof(c));
reset();
memcpy(ldp,dp,sizeof(dp));
memcpy(rdp,dp,sizeof(dp));
for(int j=;j<=m;j++) for(int i=;i<=n;i++) scanf("%d",&c[i][j]);
dp[][] = dp[][] = dp[][] = c[][];
for(int j=;j<=m;j++) dp[][j] = dp[][j-]+c[][j];
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
dp[i][j] = dp[i-][j] + c[i][j];
}
ldp[i][] = dp[i][];
for(int j=;j<=m;j++){
ldp[i][j] = max(ldp[i][j] , max(dp[i][j] , ldp[i][j-]+c[i][j]) );
}
rdp[i][m] = dp[i][m];
for(int j=m-;j>=;j--){
rdp[i][j] = max(rdp[i][j] , max(dp[i][j] , rdp[i][j+]+c[i][j]));
} for(int j=;j<=m;j++) dp[i][j] = max(dp[i][j] , max(ldp[i][j] , rdp[i][j]));
}
printf("Case #%d:\n%d\n",z,dp[n][]);
}
return ;
}
1004
最新文章
- 7. SVM松弛变量
- RQNOJ 490 环形石子合并
- DDD领域驱动设计之领域服务
- 1Z0-053 争议题目解析304
- Java基础知识学习(九)
- hdu 1541/poj 2352:Stars(树状数组,经典题)
- 【学习笔记】【oc】类和对象及类的三大基本特征
- Android面试题06
- STM32的FSMC总线复用调试笔记
- CSS不常见问题汇总
- Git 暂存区的概念
- python 接口自动化测试--框架定型(六)
- Java创建二叉搜索树,实现搜索,插入,删除操作
- ArcGIS 网络分析[2.5] VRP(车辆配送)【较难】
- Vue原理--双向数据绑定
- linux基础命令---df
- BZOJ3745 COCI2015Norma(分治)
- 常用的css选择器
- 八:The YARN Timeline Server
- C++_友元2-友元成员函数