题目大意:中文题。
解题思路:不难想的递推,dp[i][j][0]从上面过来的情况,dp[i][j][1]从下面过来的情况,然后这两种情况都可以从前一列走过来。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;
int n, m, g[N][N], dp[N][N][2];
void init () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &g[i][j]);
}
int solve () {
for (int i = 1; i <= m; i++)
dp[0][i][0] = dp[n+1][i][1] = -INF;
dp[0][1][0] = 0;
for (int i = 1; i <= n; i++) {
dp[i][1][0] = dp[i-1][1][0] + g[i][1];
dp[i][1][1] = -INF;
}
for (int j = 2; j <= m; j++) {
for (int i = 1; i <= n; i++)
dp[i][j][0] = max(dp[i-1][j][0], max(dp[i][j-1][0], dp[i][j-1][1])) + g[i][j];
for (int i = n; i >= 1; i--)
dp[i][j][1] = max(dp[i+1][j][1], max(dp[i][j-1][0], dp[i][j-1][1])) + g[i][j];
}
return max(dp[1][m][0], dp[1][m][1]);
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init ();
printf("Case #%d:\n%d\n", i, solve());
}
return 0;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
* 题目1044:Collect More Jewels,涉及到动态规划(DP)的概念。 3. 图的搜索:图的搜索算法、图的路径查找等。 * 题目1067:Gap,涉及到图的搜索算法。 * 题目1072:Nightmare,涉及到完全搜索的概念。 4. 图的...
搜索 dfs 解题代码 hdu1241
lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
HDU最全ac代码