文档章节

sicily 1563 GECKO

Ciel
 Ciel
发布于 2013/01/23 13:12
字数 624
阅读 34
收藏 0

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

分析:

本体是典型的DP类型题,每一层是一段状态,选优递推即可,相对简单而且直白。注意最后要求的是一层中的最优。当然也可以从后向前推,更省空间,这里不再优化。

代码:

// Problem#: 1563
// Submission#: 1907365
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// 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;
}

© 著作权归作者所有

上一篇: sicily 1176 Two Ends
下一篇: sicily 1083 Networking
Ciel
粉丝 3
博文 24
码字总数 18532
作品 0
程序员
私信 提问
Oracle 11g R2 ADG 搭建

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

UltraSQL
2018/07/23
0
0
使用mongoTemplate.save()报错:org.springframework.util.Assert.isTrue(ZLjava/util/function/Supplier

封装泛型接口,使用mongodb save()方法 最终还是调用 mongoTemplate.save() 方法进行保存,报以下错误:(绿色是源码的 怎么报这里错误呢?) java.lang.NoSuchMethodError: org.springframe...

小马奔腾123
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地址

我们在项目变动中通常会遇到更换git地址情况,这里介绍一个在idea项目中简单更换git地址操作: 1、点击VCS; 2、点击Git; 3、点击Remotes; 具体步骤如图 4、点击框中链接即可在右边看到一个...

west_coast
19分钟前
6
0
将规则集传递给mixin

允许包装在mixin中定义的css块。 分离的规则集是一组CSS属性、嵌套规则集、媒体声明或者是存储在变量中的任何其他内容,我们可以将它包含在规则集中或其他结构中,并且所有属性都将复制到那里...

凌兮洛
20分钟前
4
0
玩转阿里云 Terraform(一):Terraform 是什么

从本文起,我将陆续推出一系列有关 Terraform 的文章,从概念,特点,工作机制,用法以及最佳实践等多个方面由浅入深的向大家介绍如何在阿里云上玩转 Terraform。同时也希望借此机会,与感兴...

阿里云官方博客
21分钟前
4
0
科研大数据面临的挑战

近几十年硬件的发展非常迅猛,第一台Macintosh苹果电脑的内存是128KB(0.13MB),现在很多笔记本配的是8GB的内存,硬盘1TB(1024GB),2TB的很常见。大型的数据服务器上还会有更大的储容量,...

英论阁学术院
21分钟前
5
0
python学习10.09:Python列表和元组的底层实现

有关列表(list)和元组(tuple)的底层实现,本节分别从它们的源码来进行分析。 首先来分析 list 列表,它的具体结构如下所示: typedef struct { PyObject_VAR_HEAD /* Vector o...

太空堡垒185
22分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部