文档章节

计蒜客 蓝桥杯模拟 瞬间移动 dp

o
 osc_n6euf5h6
发布于 2019/03/19 19:48
字数 570
阅读 14
收藏 0

精选30+云产品,助力企业轻松上云!>>>

 

在一个 n \times mn×m 中的方格中,每个格子上都有一个分数,现在蒜头君从 (1,1)(1,1) 的格子开始往 (n, m)(n,m) 的格子走。要求从 (x_1,y_1)(x1,y1) 到 (x_2,y_2)(x2,y2) ,满足 x_2 \ge x_1,\ y_2 \ge y_1x2x1, y2y1 。请问蒜头君从 (1,1)(1,1) 的点到 (n,m)(n,m) 最多可以得多少分?

每个格子的分数只能得到一次,其中 (1,1)(1,1) 和 (n,m)(n,m) 是必须要走的两个格子,(1,1)(1,1) 表示第一行第一列的方格。

输入格式

第一行输入两个整数 n,mn,m ,表示有 n\times mn×m 个方格。

接下来输入 nn 行 mm 列个整数 gradegrade 。

数据范围与约定

对于 100\%100% 的数据,-300 \le grade \le 300300grade300。

对于 30\%30% 的数据, 1 \le n,m \le 51n,m5 。

对于 60\%60% 的数据, 1 \le n,m \le 601n,m60 。

对于 100\%100% 的数据, 1 \le n,m \le 5001n,m500

输出格式

输出一个整数表示蒜头君能获取到的最大分数。

样例输入复制

3 3
1 2 3
4 5 6
7 8 9

样例输出复制

29

题解:
很容易的想到dp表达式 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]
但是这题目的意思是每个格子的分数可要可不要,(1,1),(n,m)格子的分数必须要
所以在代码中得加几个判断,除(1,1),(n,m)外的其他小于0的分数都不要
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e3+10;
const ll mod = 1e9+7;
const double pi = acos(-1.0);
const double eps = 1e-8;
ll n, m, a[maxn][maxn], dp[maxn][maxn];
int main() {
    scanf("%lld%lld",&n,&m);
    for( ll i = 1; i <= n; i ++ ) {
        for( ll j = 1; j <= m; j ++ ) {
            scanf("%lld",&a[i][j]);
        }
    }
    for( ll i = 1; i <= n; i ++ ) {
        for( ll j = 1; j <= m; j ++ ) {
            if( ( i == 1 && j == 1 ) || ( i == n && j == m ) ) {
                dp[i][j] = a[i][j] + max(dp[i-1][j],dp[i][j-1]);
            } else {
                dp[i][j] = max((ll)0,a[i][j]) + max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

  

上一篇: 坏台阶问题
下一篇: Django与Ajax
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

SnailSVN Pro for mac(SVN客户端) v1.9.9

macw为您带来SnailSVN Pro for mac ,SnailSVN Mac版是一款类似于 TortoiseSVN 的 Apache Subversion(SVN)客户端,与 Finder 紧密集成。SnailSVN Mac版允许你从 Finder 的上下文菜单中快速...

单手绕月
13分钟前
0
0
python网络编程(进程与多线程)

multiprocessing模块   由于GIL的存在,python中的多线程其实并不是真正的多线程,如果想要充分地使用多核CPU的资源,在python中大部分情况需要使用多进程。   multiprocessing包是Pytho...

osc_ky74f26k
13分钟前
0
0
CentOS7 redis5.0高可用部署

概述 Redis Sentinel为Redis提供高可用性。Redis Sentinel是一个分布式系统,Sentinel本身设计为在有多个Sentinel进程协同合作的配置中运行。具有多个Sentinel进程进行协作的优点如下: 1、当...

紅顏為君笑
13分钟前
0
0
Ocelot简易教程(四)之请求聚合以及服务发现

上篇文章给大家讲解了Ocelot的一些特性并对路由进行了详细的介绍,今天呢就大家一起来学习下Ocelot的请求聚合以及服务发现功能。希望能对大家有所帮助。 作者:依乐祝 原文地址:https://www...

osc_zo0djpuu
14分钟前
0
0
leetcode63(不同路径 II)--Java语言实现

求: 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。 现在...

拓拔北海
14分钟前
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部