2016年2月24日 星期三

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

File failed to load: file:///C:/Users/user/Desktop/Dropbox/HSNU%20Online%20Judge/192_files/extensions/MathMenu.js
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:
TestTimeMemoryScore
0-11000ms262144kb
0-21000ms262144kb
0-31000ms262144kb
1-11000ms262144kb10
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
2-11000ms262144kb10
2-21000ms262144kb
2-31000ms262144kb
2-41000ms262144kb
3-11000ms262144kb10
3-21000ms262144kb
4-11000ms262144kb10
4-21000ms262144kb
51000ms262144kb10
61000ms262144kb10
75000ms262144kb10
85000ms262144kb10
95000ms262144kb10
10-15000ms262144kb10
10-25000ms262144kb

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原