心剑菩提 发表于 2008-8-20 08:10

Gondar哪位来看看问题出在哪里？

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]]

卧龙孔明 发表于 2008-8-20 10:54

多进程dp

心剑菩提 发表于 2008-8-20 20:17

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

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

心剑菩提 发表于 2008-8-21 13:28

哪位来看看问题在哪里？

#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;
}

页: [1]

编程论坛