描述 Description
最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第 i 块馅饼中含有 Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。 奶牛们把所有烤好的馅饼在草地上排成了一个 R 行 (1<=R<=100)C 列(1<=C<=100) 的矩阵。你现在站在坐标为 (1,1) 的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为 (R,C) 的馅饼旁边停止走动。每做一次移动，你必须走到下一列的某块馅饼旁边，并且，行数的变动不能超过 1（也就是说，如果现在你站在坐标为 (r,c) 的馅饼边上，下一步你可以走到坐标为 (r-1,c+1),(r,c+1), 或者(r+1,c+1) 的馅饼旁边）。当你从一块馅饼边经过，你就可以拿走馅饼里所有的金币。当然啦，你一定不会愿意因半路离开草地而失去唾手可得的金币，但，最终你一定得停在坐标为 (R,C) 的馅饼旁边。 现在，你拿到了一张标记着馅饼矩阵中，每一块馅饼含金币数量的表格。那么，按照规则，你最多可以拿到多少金币呢？ 比方说，奶牛们把馅饼排成如下的矩阵，矩阵中的数字表示该位置的馅饼中含金币的数量：
6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8
以下是条合法的路线
按上述的路线进行走动，一共可以获得 6+4+9+9+6+5+8=47 个金币．按照规则，在这个矩阵中最多可以得到 50 个金币，路线如下图所示：
输入格式 InputFormat
第 1 行: 两个用空格隔开的整数，R 和 C.
第 2..R+1 行: 每行包含 C 个用空格隔开的正整数，依次表示一行中从左往右各 个馅饼里金币的数量.
输出格式 OutputFormat
第 1 行: 输出一个正整数，表示你所能收集到的最大金币数目.
样例输入 SampleInput
10 20
1 8 11 18 15 17 8 16 3 14 9 11 3 18 21 3 3 21 20 7
7 18 2 21 22 6 8 16 25 19 25 22 19 11 18 13 10 14 17 3
9 6 21 23 2 3 15 17 22 17 4 8 16 1 6 23 21 2 9 16
1 22 10 25 4 9 20 10 18 24 16 1 13 5 3 13 7 11 11 1
5 17 8 1 13 9 5 4 16 10 21 25 3 11 19 10 19 14 10 25
23 23 14 9 13 5 10 8 18 7 9 22 25 24 7 14 6 7 4 4
12 5 23 15 20 21 3 4 7 14 6 1 11 1 7 23 8 20 11 10
14 25 5 21 10 17 1 21 22 5 15 18 1 18 21 3 14 8 18 9
14 4 19 8 23 17 13 5 20 19 19 14 23 18 2 3 6 12 2 7
19 15 19 24 15 21 17 25 19 1 23 19 6 11 6 21 11 8 5 25
样例输出 SampleOutput
354
代码 Code
注意能走到的只能是对角线以上的部分。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a[105][105],f[105][105];
int c;
int main()
{
memset(f,0,sizeof(f));
scanf("%d%d",&r,&c);
for (i=1;i<=r;i++) for (j=1;j<=c;j++) scanf("%d",&a[i][j]);
f[1][1]=a[1][1];
for (j=2;j<=c;j++) for (i=1;i<=j;i++)
{
f[i][j]=max(f[i-1][j-1],max(f[i][j-1],f[i+1][j-1]))+a[i][j];
}
printf("%d\n",f[r][c]);
return 0;
}