本篇文章主要介绍了"Filthy Rich（动态规划）"，主要涉及到Filthy Rich（动态规划）方面的内容，对于Filthy Rich（动态规划）感兴趣的同学可以参考一下。
Limit: 10000/5000 MS
Limit: 32768/32768 K (Java/Others)
They say that in Phrygia, the streets are paved with gold. You’re
currently on vacation in Phrygia, and to your astonishment you
discover that this is to be taken literally: small heaps of gold
are distributed throughout the city. On a certain day, the
Phrygians even allow all the tourists to collect as much gold as
they can in a limited rectangular area. As it happens, this day is
tomorrow, and you decide to become filthy rich on this day. All the
other tourists decided the same however, so it’s going to get
crowded. Thus, you only have one chance to cross the field. What is
the best way to do so?
Given a rectangular map and amounts of gold on every field,
determine the maximum amount of gold you can collect when starting
in the upper left corner of the map and moving to the adjacent
field in the east, south, or south-east in each step, until you end
up in the lower right corner.
The input starts with a line containing a single integer, the
number of test cases.
Each test case starts with a line, containing the two integers r
and c, separated by a space (1 <= r, c
<= 1000). This line is followed by r rows, each
containing c many integers, separated by a space. These integers
tell you how much gold is on each field. The amount of gold never
The maximum amount of gold will always fit in an int.
For each test case, write a line containing “Scenario #i:”, where i
is the number of the test case, followed by a line containing the
maximum amount of gold you can collect in this test case. Finish
each test case with an empty line.
1 10 8
0 0 1
0 27 0
a,int b,int c)
a:b)>c? (a>b? a:b):c;