[HOJ 192][Codeforces #131]撿肥皂 (題目備份)

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/192_files/extensions/MathMenu.js

HSNU Online Judge

• Index
• User
• Problem
• Status
• Contest
• Course
• Discuss_Ura

HOJ生病惹QQ，因此在此悼念昔日光彩

題目備份，請參考～

題解在這裡

敬告：目前HOJ主機也許進入瀕死狀態了，常常無預警跳電。請看到這則公告的人能注意備份自己的資料，感謝。
至於主機壞掉以後會如何目前並沒有任何規劃.. 

Submit　　Ranklist

Problem : 192 - 撿肥皂

Problem Statistics

Solved Member: 30　　Submission: 127　　User Tried: 34

Problem：

hanhan 與他的好朋友 nahnah 在撿肥皂。

某天，他們到了一張充滿肥皂的地圖上。地圖可以用 n*n 的方格來表示。最初 hanhan 與 nahnah 都位於最左上角的格子上，他們各自都可以向上下左右四個方向移動，兩人都需要不繞路的走到地圖的右下角。

每個格子上都有一個值，代表第一個到這格的人會得到的肥皂數(或者負的，代表會減少)，當一個格子被其中一個人走過之後下次變不會再撿到肥皂了。由於 hanhan 以及 nahnah 不能沒有肥皂，所以一當他的肥皂數被降到 0 以下時，他會先融資來償還被減少的肥皂，假設他一共欠了 x 個肥皂，我們仍然以 -x 來表示他所擁有的肥皂數。

請你幫 hanhan 與 nahnah 各規劃一條路徑，使得他們沿路走到右下角能擁有最多的肥皂數。

Input：

第一行有一個整數 n(1 ≤ n ≤ 300)，代表地圖的大小。
接下來有 n 行，每行有 n 個整數Vij ( -1000 ≤ n ≤ 1000 ) ，分別代表每個格子有多少數量的肥皂。

Output：

輸出一個數字，代表兩人走到終點之後最多總共能擁有多少肥皂。

Sample Input：

SAMPLE A:
1
5

SAMPLE B:
2
11 14
16 12

SAMPLE C:
3
25 16 25
12 18 19
11 13 8

Sample Output：

SAMPLE A:
5

SAMPLE B:
53

SAMPLE C:
136

HINT：

20% 測資滿足: n ≤ 30且所有格子肥皂數皆為正數或0。
40% 測資滿足: n ≤ 30
40% 測資滿足: 所有格子的肥皂數皆為正數或0

SAMPLE C:

兩種顏色的路徑分別代表 hanhan 與 nahnah 所走的路線。

Source：

Codeforces #131

Problem Setter

Nekosyndrome

Testdata：

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
0-3	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
2-1	1000ms	262144kb	10
2-2	1000ms	262144kb
2-3	1000ms	262144kb
2-4	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
4-1	1000ms	262144kb	10
4-2	1000ms	262144kb
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7	5000ms	262144kb	10
8	5000ms	262144kb	10
9	5000ms	262144kb	10
10-1	5000ms	262144kb	10
10-2	5000ms	262144kb

HSNU Online Judge System
推薦瀏覽環境: Firefox 4
頁面讀取時間: 0.2652 秒，使用記憶體: 2.87MB 。