KIDx的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2845
题意:在图中取数,例如取了81之后,同一行的相邻两个不能取,还有81的上面那行和下面那行也不能取,问能取到的最大和是多少?
解析:对于一行来说,相邻的数不可同时取,
容易得到状态转移方程:sum[i] = max (sum[i-2]+sum[i], sum[i-1])(i>=2,注意i从1开始,i-2=0时不存在sum[i-2]相当于只取sum[i]),初始时sum[0] = 0, sum[i]就是第i个数
而对于一列来说,显然的也是相邻的不能取,所以对每一行处理完后再用每行得到结果组成一列进行同样处理即可得出答案
#include <iostream>
using namespace std;
#define M 200005
int a[M], b[M];
int main()
{
int m, n, i, j;
while (~scanf ("%d%d", &m, &n))
{
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
scanf ("%d", b+j);
for (j = 2; j <= n; j++)
b[j] = max (b[j-2]+b[j], b[j-1]);
a[i] = b[n];
}
for (i = 2; i <= m; i++)
a[i] = max (a[i]+a[i-2], a[i-1]);
printf ("%d\n", a[m]);
}
return 0;
}
- 大小: 13 KB
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类