问题2950--Cow Pie Treasures

2950: Cow Pie Treasures

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

题目描述

The cows have been busily baking pies that contain gold coins! Each pie has some number N_i (1 <= N_i <= 25) of gold coins and is neatly labeled on its crust with the number of gold coins inside. The cows have placed the pies very precisely in an array of R rows and C columns (1 <= R <= C <= 100) out in the pasture. You have been placed in the pasture at the location (R=1,C=1) and have gathered the gold coins in that pie. You must make your way to the other side of the pasture, moving one column closer to the end point (which is location (R,C)) with each move you make. As you step to the new column, you may stay on the same row or change your row by no more than 1 (i.e., from (r,c) you can move to (r-1,c+1), (r,c+1), or (r+1,c+1). Of course, you would not want to leave the field and fail to get some gold coins, and you must end up at (R,C). Given a map of the pasture, what is the greatest number of gold coins you can gather? By way of example, consider this field of gold-bearing cow pies:
start-> 6 5 3 7 9 2 7
        2 4 3 5 6 8 6
        4 9 9 9 1 5 8 <-end
Here's one path:
start-> 6 5 3 7 9 2 7
         \
        2 4 3 5 6 8 6
           \   / \
        4 9 9-9 1 5-8 <-end
The path above yields 6+4+9+9+6+5+8 = 47 gold coins. The path below is even better and yields 50 coins, which is the best possible:
start-> 6 5 3 7 9 2 7
         \
        2 4 3 5 6-8 6
           \   /   \
        4 9 9-9 1 5 8 <-end

输入

* Line 1: Two space-separated integers: R and C * Lines 2..R+1: Each line contains C space-separated small integers in the obvious order

输出

* Line 1: An integer (which fits easily into 32 bits) that is the maximum number of gold coins that can be gathered

样例输入 Copy

3 7
6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8

样例输出 Copy

50

来源/分类