Time Limit:1000MS Memory Limit:65536K
Total Submit:0 Accepted:0

Description

Gardon和Gondar上学去的路上，发现地上遍地都是鲜美的蘑菇！Gardon和Gondar在(0,0)位置，他们要去(m-1,n-1)的位置去上学，由于已经快上课了，所以他们必须走最短的路过去，但是地上的蘑菇又实在太诱人了，所以他们决定分头去采。他们每次可以向下或者向右走一格，走到一格的时候就采光那里所有的蘑菇；如果他们中间的时候走到一起，该地点上蘑菇也只能被采一次；直到走到教室为止。你能计算下按照这样的规则，他们加在一起最多能采到多少蘑菇么？

Input

输入包含多组数据，数据的第一行有两个整数，m和n。接下来的m行每行有n个整数，表示了每个地点蘑菇的数目。已知起点(0,0)和终点(m-1,n-1)都一定没有蘑菇。所有的整数都是非负数且都不超过100。
输入以两个0作为结束。

Output

对于输入的每组数据，输出一个整数，为Gardon和Gondar所能采到的最多的蘑菇数目。

Sample Input


4 4
0 1 1 0
1 0 1 1
0 1 1 0
1 0 1 0
0 0

Sample Output


8

Hint

1 1 1 0
0 0 1 1
0 0 0 1
0 0 0 1

2 0 0 0
2 0 0 0
2 2 2 0
0 0 2 0

这两个表表示Gardon和Gondar要走的路线。

[[it] 本帖最后由 心剑菩提 于 2008-8-21 15:21 编辑 [/it]]

恩，知道DP,但状态方程？

[[it] 本帖最后由 心剑菩提 于 2008-8-21 13:26 编辑 [/it]]

#include"stdio.h"
#include"string.h"
#define max(x,y) (x>y?x:y)
int main()
{
    int i,j;
    int n,m;
    int map[100][100];
    int ans[100][100];
    while(scanf("%d%d",&m,&n)&&n&&m)
    {
        memset(map,0,sizeof(map));
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)  scanf("%d",&map[i][j]);
        memset(ans,0,sizeof(ans));
        for(i=0;i<m;i++)
            for(j=i+1;j<n;j++)
            {
                if(i==0)    ans[i][j]=ans[i][j-1]+map[i][j];//上边线问题（只能是由左继承）
                else
                {
                  if(j-i==1)ans[i][j]=ans[i-1][j]+map[i][j];//中对角线的边线问题（只能上继承）  
                  else        ans[i][j]=max(ans[i-1][j],ans[i][j-1])+map[i][j];//(转移动态方程)         
                }
            }            
        for(i=1;i<m; i++)
            for(j=0;j<=i;j++)
            {
                if(j==0) ans[i][j]=ans[i-1][j]+map[i][j];//左边界问题(只由上继承)
                else           
                {
                    if(j==i)   ans[i][j]=ans[i][j-1]+map[i][j];//中对角线的边界问题(只能左继承)
                    else       ans[i][j]=max(ans[i-1][j],ans[i][j-1])+map[i][j];//(转移动态方程)
                }
            }
            printf("\n");
        /*for(i=0;i<m;i++)
        {
             for(j=0;j<n;j++)
                 printf("%d  ",ans[i][j]);
             printf("\n");
        }*/
        printf("%d\n",ans[m-2][n-1]+ans[m-1][n-2]);//二路合并。
    }
    return 0;
}