Happy birthday

Problem Description
Today is Gorwin’s birthday. So her mother want to realize her a wish. Gorwin says that she wants to eat many cakes. Thus, her mother takes her to a cake garden.

The garden is splited into n*m grids. In each grids, there is a cake. The weight of cake in the i-th row j-th column is wij kilos, Gorwin starts from the top-left(1,1) grid of the garden and walk to the bottom-right(n,m) grid. In each step Gorwin can go to right or down, i.e when Gorwin stands in (i,j), then she can go to (i+1,j) or (i,j+1) (However, she can not go out of the garden).

When Gorwin reachs a grid, she can eat up the cake in that grid or just leave it alone. However she can’t eat part of the cake. But Gorwin’s belly is not very large, so she can eat at most K kilos cake. Now, Gorwin has stood in the top-left grid and look at the map of the garden, she want to find a route which can lead her to eat most cake. But the map is so complicated. So she wants you to help her.

Input
Multiple test cases (about 15), every case gives n, m, K in a single line.

In the next n lines, the i-th line contains m integers wi1,wi2,wi3,⋯wim which describes the weight of cakes in the i-th row

Please process to the end of file.

[Technical Specification]

All inputs are integers.

1<=n,m,K<=100

1<=wij<=100

Output
For each case, output an integer in an single line indicates the maximum weight of cake Gorwin can eat.

Sample Input
1 1 2
3
2 3 100
1 2 3
4 5 6

Sample Output
0
16

3个回答

应该是二维数组的题吧,我这小学英语不够用了啊....

??走15次,每次只许移动一个格子,或横或竖,然后在输入这个小姑娘能吃的蛋糕重量,
实在不知道要干嘛了...难道我要去中学上英语课去了么?不能够啊!!!!

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐