一道算法题目Gardon和Gondar上学去的路上,发现地上遍地都是鲜美的蘑菇!Gardon和Gondar在(0,0)位置,他们要去(m-1,n-1)的位置去上学,由于已经快上课了,所以他们必须走最短的路过去,但是地上的蘑菇

Question

一道算法题目
Gardon和Gondar上学去的路上,发现地上遍地都是鲜美的蘑菇!Gardon和Gondar在(0,0)位置,他们要去(m-1,n-1)的位置去上学,由于已经快上课了,所以他们必须走最短的路过去,但是地上的蘑菇又实在太诱人了,所以他们决定分头去采.他们每次可以向下或者向右走一格,走到一格的时候就采光那里所有的蘑菇；如果他们中间的时候走到一起,该地点上蘑菇也只能被采一次；直到走到教室为止.你能计算下按照这样的规则,他们加在一起最多能采到多少蘑菇么?
Input
输入包含多组数据,数据的第一行有两个整数,m和n.接下来的m行每行有n个整数,表示了每个地点蘑菇的数目.已知起点(0,0)和终点(m-1,n-1)都一定没有蘑菇.所有的整数都是非负数且都不超过5.
输入以两个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

Answer 1

我不知道楼上在干什么.

这道题和 noip2008传纸条 以及 noip2000方格取数 本质上是一样的.建议百度一下.

解题报告中使用的是dp的方法.

考虑若果是k条路径,那么可以使用费用流的方法.

具体参考BYvoid的博客

https://www.byvoid.com/blog/noip2008-message-costflow/

我在这里似乎什么都没有干.

(费用流是什么?以后你会了解到的.)