sicily 1563 GECKO 原

Ciel

Description

During the rainy season, one of the walls in the house is infested with mosquitoes. The wall is covered by h × w square tiles, where there are h rows of tiles from top to bottom, and w columns of tiles from left to right. Each tile has 1 to 1000 mosquitoes resting on it.

A gecko wants to eat as many mosquitoes as possible, subject to the following restrictions. It starts by choosing any tile in the top row, and eats the mosquitoes in that tile. Then, it moves to a tile in the next lower row, eats the mosquitoes on the tile, and so on until it reaches the floor. When it moves from one tile to a tile in the next lower row, it can only move vertically down or diagonally to the left or right .

Given the values of h and w, and the number of mosquitoes resting on each tile, write a program to compute the maximum possible number of mosquitoes the gecko can eat in one single trip from the top to the bottom of the wall.

Input

The first line has two integers. The first integer h (1 <= h <= 500) is the number of rows of tiles on the wall. The second integer w (1 <= w <= 500)is the number of columns of tiles on the wall.  Next, there are h lines of inputs. The ith line specifies the number of mosquitoes in each tile of the top ith row. Each line has w integers, where each integer m (1 <= m <= 1000) is the number mosquitoes on that tile. The integers are  separated by a space character.

Output

The output file contains a single integer, which is the maximum possible number of mosquitoes the gecko can eat in one single trip from the top to the bottom of the wall.

Sample Input

``````6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 7 2 5 1``````

Sample Output

``32``

代码：

``````// Problem#: 1563
// Submission#: 1907365
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <iostream>
using namespace std;

#define MAX 500

int wall[MAX][MAX];
int move[3][2] = {{-1, -1}, {-1, 0}, {-1, 1}};
int dp[MAX][MAX] = {0};
int h, w;

inline bool judge(int x, int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}

inline int max(int x, int y) {
int a, b, m;
m = 0;
for (int i = 0; i < 3; ++i) {
a = x + move[i][0];
b = y + move[i][1];
if (judge(a, b) && dp[a][b] > m) m = dp[a][b];
}
return m;
}

int main() {
cin >> h >> w;
int re = 0;
for (int i = 0; i < h; ++i)
for (int j = 0; j < w; ++j)
cin >> wall[i][j];
for (int i = 0; i < w; ++i)
dp[0][i] = wall[0][i];
for (int i = 1; i < h; ++i) {
for (int j = 0; j < w; ++j) {
dp[i][j] = max(i, j) + wall[i][j];
}
}
for (int i = 0; i < w; ++i)
if (dp[h - 1][i] > re) re = dp[h - 1][i];
cout << re << endl;
return 0;
}``````

Ciel

--============Oracle ADG搭建============== --==========准备阶段========= 1.检查primary为archivelog模式。 select log_mode from v\$database; 如果为noarchivelog模式，切换到archivelo......

UltraSQL
2018/07/23
0
0

2018/01/10
3K
1
centos6.8时间设置与同步

[root@bogon ~]# rm /etc/localtime [root@bogon ~]# ln -s /usr/share/zoneinfo/Asia/Shanghai /etc/localtime [root@bogon ~]# date Thu Sep 14 08:54:32 CST 2017 [root@bogon ~]# yum in......

argen2020
2017/09/14
0
0
PureScript 0.7.5.1/0.7.5.2 发布

PureScript 0.7.5.1/0.7.5.2 发布。0.7.5.1 的更新如下： Fix #1169, #1315, #1534, #1543, #1548, #1551, #1557, #1570 Fix memory leak caused by WriterT (#1297) by @paf31 Display hin......

oschina
2015/10/28
680
0
Puma 3.12.0 发布，为并发而生的 Ruby Web 服务器

Puma 3.12.0 已发布，该版本包含 5 个新特性和 2 项 bug 修复。详细如下： 5 features: 现在可以指定服务器应支持的 SSL cipher Puma 的 设置现在位于 Pool capacity 现在位于 要求 Ruby 2.2...

2018/07/15
430
0

idea修改新的git地址

west_coast
19分钟前
6
0

20分钟前
4
0

21分钟前
4
0

21分钟前
5
0
python学习10.09：Python列表和元组的底层实现

22分钟前
4
0