【问题描述】

一个城市的道路成了像棋盘那样的网状，南北向的路有n条，并由西向东从1标记到n,东西向的路有m条，并从南向北从1标记到m,每一个交叉点代表一个路口，有的路口有正在等车的乘客。一辆公共汽车将从(1,1)点驶到（n,m）点，车只能向东或者向北开.

写一个程序，告诉司机怎么走能接到最多的乘客。


第一行是n,m,和k,其中k是有乘客的路口的个数。

以下k行是有乘客的路口的坐标和乘客的数量。

每行内相邻两元素用一个空格隔开

【输出】

接到的最多的乘客数。

【输入输出样例】

bus.in
 

bus.out

8 7 11

4 3 4

6 2 4

2 3 2

5 6 1

2 5 2

1 5 5

2 1 1

3 1 1

7 7 1

7 4 2

8 6 2
 

11

【数据范围限制】

100%的数据：1 <= n <= 103, 1 <= m <= 103, 1 <= k <= 103；

每个路口的乘客数量不超过1000000。
求思路代码我自己实现!

把每个点的乘客数记为value, 从这个点出发能拉到最多的乘客数记为f,状态转移方程:

f[i,j] = MAX(f[i+1,j], f[i,j+1]) + value[i,j];

收到的鲜花

• rjsp 于 2015-09-09 11:08 送鲜花  10朵   附言：我很赞同

#include <stdio.h>

int main( void )
{
    // 输入信息
    unsigned n = 8;
    unsigned m = 7;
    unsigned matrix[104][104] = { 0 };
    matrix[4][3] = 4;
    matrix[6][2] = 4;
    matrix[2][3] = 2;
    matrix[5][6] = 1;
    matrix[2][5] = 2;
    matrix[1][5] = 5;
    matrix[2][1] = 1;
    matrix[3][1] = 1;
    matrix[7][7] = 1;
    matrix[7][4] = 2;
    matrix[8][6] = 2;
    // 算法
    for( unsigned i=1; i<=n; ++i )
        for( unsigned j=1; j<=m; ++j )
            matrix[i][j] += (matrix[i-1][j]>matrix[i][j-1] ? matrix[i-1][j] : matrix[i][j-1]);
    // 输出结果
    printf( "%u\n", matrix[n][m] );

    return 0;
}

大神