[题目描述:]
正处在某一特定时期之中的李大水牛由于消化系统比较发达, 最近一直处在饥饿的状态中. 某日上课, 正当他饿得头昏眼花之时, 眼前突然闪现出了一个 n*m(n and m<=200)的矩型的巨型大餐桌, 而自己正处在这个大餐桌的一侧的中点下边. 餐桌被划分为了 n*m 个小方格, 每一个方格中都有一个圆形的巨型大餐盘, 上面盛满了令李大水牛朝思暮想的食物. 李大水牛已将餐桌上所有的食物按其所能提供的能量打了分(有些是负的, 因为吃了要拉肚子), 他决定从自己所处的位置吃到餐桌的另一侧, 但他吃东西有一个习惯 -- 只吃自己前方或左前方或右前方的盘中的食物.
由于李大水牛已饿得不想动脑了, 而他又想获得最大的能量, 因此, 他将这个问题交给了你.
每组数据的出发点都是最后一行的中间位置的下方!
[输入格式:]
第一行为 m n.(n 为奇数), 李大水牛一开始在最后一行的中间的下方
接下来为 m*n 的数字距阵.
共有 m 行, 每行 n 个数字. 数字间用空格隔开. 代表该格子上的盘中的食物所能提供的能量.
数字全是整数.
[输出格式:]
一个数, 为你所找出的最大能量值.
[算法分析:]
显然是二维 DP, 设 f[i][j]表示走到点 (i, j) 时的最大能量, a[i][j]表示点 (i, j) 的能量
则 DP 方程为:
f[i][j] = max{f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]} + a[i][j]
有一 (很) 些(多)细节需要注意:
最后的答案并不是 max{f[n][i]}, 因为李大水牛只能走到前方, 左前方和右前方
保证读入的列数 m 是奇数时, 最中间的位置为[m / 2] + 1 而不是[m / 2]
- [Code:]
- //Likecloud - 吃, 吃, 吃
- #include<iostream>
- #include<cstdio>
- #define re register
- using namespace std;
- const int MAXN = 200 + 1;
- int n, m, ans;
- int a[MAXN][MAXN];
- int f[MAXN][MAXN];
- inline int read() {
- int x=0, f=1; char ch=getchar();
- while(ch<'0' || ch>'9') {
- if(ch == '-') f = -1;
- ch = getchar();
- }
- while(ch>='0' && ch<='9')
- x=(x<<3) + (x<<1) + ch-48, ch = getchar();
- return x * f;
- }
- inline int Max(int a, int b, int c) {
- return max(max(a, b), c);
- }
- int main() {
- n = read(), m = read();
- for(re int i=1; i<=n; ++i)
- for(re int j=1; j<=m; ++j)
- a[i][j] = read();
- for(re int i=1; i<=m; ++i) f[1][i] = a[1][i];
- for(re int i=2; i<=n; ++i)
- for(re int j=1; j<=m; ++j)
- f[i][j] = Max(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + a[i][j];
- int ans = Max(f[n][m / 2 + 1], f[n][(m / 2)], f[n][(m / 2) + 2]);
- printf("%d\n", ans);
- }
[洛谷] [动态规划(二维)] P1508 Likecloud - 吃, 吃, 吃
来源: http://www.bubuko.com/infodetail-2610426.html