专栏首页数据结构与算法P1508 Likecloud-吃、吃、吃

P1508 Likecloud-吃、吃、吃

题目背景

问世间,青春期为何物?

答曰:“甲亢,甲亢,再甲亢;挨饿,挨饿,再挨饿!”

题目描述

正处在某一特定时期之中的李大水牛由于消化系统比较发达,最近一直处在饥饿的状态中。某日上课,正当他饿得头昏眼花之时,眼前突然闪现出了一个n*m(n and m<=200)的矩型的巨型大餐桌,而自己正处在这个大餐桌的一侧的中点下边。餐桌被划分为了n*m个小方格,每一个方格中都有一个圆形的巨型大餐盘,上面盛满了令李大水牛朝思暮想的食物。李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的,因为吃了要拉肚子),他决定从自己所处的位置吃到餐桌的另一侧,但他吃东西有一个习惯——只吃自己前方或左前方或右前方的盘中的食物。

由于李大水牛已饿得不想动脑了,而他又想获得最大的能量,因此,他将这个问题交给了你。

每组数据的出发点都是最后一行的中间位置的下方!

输入输出格式

输入格式:

[输入数据:]

第一行为m n.(n为奇数),李大水牛一开始在最后一行的中间的下方

接下来为m*n的数字距阵.

共有m行,每行n个数字.数字间用空格隔开.代表该格子上的盘中的食物所能提供的能量.

数字全是整数.

输出格式:

[输出数据:]

一个数,为你所找出的最大能量值.

输入输出样例

输入样例#1:

6 7
16 4 3 12 6 0 3
4 -5 6 7 0 0 2
6 0 -1 -2 3 6 8
5 3 4 0 0 -2 7
-1 7 4 0 7 -5 6
0 -1 3 4 12 4 2

输出样例#1:

41

说明

快吃!快吃!快吃!

记忆化搜索,注意x==1的情况

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN=233;
 8 void read(int &n)
 9 {
10     char c='+';int x=0;bool flag=0;
11     while(c<'0'||c>'9')
12     {c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')
14     {x=x*10+(c-48);c=getchar();}
15     flag==1?n=-x:n=x;
16 }
17 int n,m;
18 int a[MAXN][MAXN];
19 int dp[MAXN][MAXN];
20 int xx[5]={-1,-1,-1};
21 int yy[5]={-1,0,+1};
22 int M_S(int x,int y)
23 {
24     if(x==1)
25     {
26         if(!dp[x][y])
27             dp[x][y]=a[x][y];
28         return dp[x][y];
29     }
30         
31     if(dp[x][y])
32         return dp[x][y];
33     for(int i=0;i<3;i++)
34     {
35         int wx=x+xx[i];
36         int wy=y+yy[i];
37         if(wx>=1&&wx<=n&&wy>=1&&wy<=m)
38         dp[x][y]=max(dp[x][y],M_S(wx,wy)+a[x][y]);
39     }
40     return dp[x][y];
41 }
42 int main()
43 {
44     read(n);read(m);
45     for(int i=1;i<=n;i++)
46         for(int j=1;j<=m;j++)
47             read(a[i][j]);
48     M_S(n,m/2+1);
49     M_S(n,m/2);
50     M_S(n,m/2+2);
51     int ans=max(max(dp[n][m/2],dp[n][m/2+1]),dp[n][m/2+2]);
52     printf("%d",ans);
53     return 0;
54 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf1043D. Mysterious Crime(二分 前缀和)

    因此我们按照\(x - y\)排序,对于每个位置,肯定是某一个前缀全选\(x+b\),除此之外都是\(y+a\)

    attack
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • P1040 加分二叉树

    题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节...

    attack
  • cf1043D. Mysterious Crime(二分 前缀和)

    因此我们按照\(x - y\)排序,对于每个位置,肯定是某一个前缀全选\(x+b\),除此之外都是\(y+a\)

    attack
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • 第二十三节:Java语言基础-详细讲解函数与数组

    函数在Java中称为方法,在其他语言中可能称为函数,函数,方法就是定义在类中具有特定功能的程序。函数,在Java中可称为方法。

    达达前端
  • Hamming Distance

    Tyan
  • HDU 2444 The Accomodation of Students(二分图判断+最大匹配数)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2444

    Ch_Zaqdt
  • Codeforces Round #535 (Div. 3) B. Divisors of Two Integers(思维)

    题目链接:http://codeforces.com/contest/1108/problem/B

    Ch_Zaqdt
  • P1040 加分二叉树

    题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节...

    attack

扫码关注云+社区

领取腾讯云代金券