TopCoder

User's AC Ratio

100.0% (20/20)

Submission's AC Ratio

63.5% (33/52)

Description

在贏得世上所有的資訊競賽後,Peter Hacker開始想要嘗試新的挑戰。因此他在俄羅斯的密碼學線上競賽中以"VerhShifr"為隊名報名了,並且很快的晉級到了在莫斯科的決賽。

在主辦單位主辦的參訪活動中,他們參觀了俄羅斯娃娃博物館。這個博物館中有非常多奇怪的迷宮。迷宮中都是方型的,而且牆壁都是南北向或東西向。每個展場的四個方向都有個門,博物館的最西北方是入口,最東南方則是出口。

俄羅斯的國手隊準備了有趣的遊戲和他們的對手玩。他們在每間房間放了一個獨特大小的俄羅斯娃娃。每個人必須要走過迷宮,並且收集盡可能多的娃娃,將他們一個一個裝起來。當然參賽者可以決定是否要拿某個房間的娃娃(當然要可以包住你手上最後拿的)或直接繼續往前走。

為了增加難度,一個裁判將每間房間改成只能從東方跟南方出去。Peter當然也對這些限制非常的苦惱。因此他寫了一個可以找到最佳路的程式。

現在請問你是否也能寫出這個程式呢?給你每個房間的娃娃大小,請你寫一個程式去計算最多可以拿到幾個娃娃。


After wining every informatics competition in the world, Peter the Hacker decided to try a different type of challenge. He registered in the Russian web site for online competitions in cryptography and locksmith “VerhShifr” and soon he has arrived in Moscow, participating in the finals.
During one of the excursions that the organizers prepared, the group visited a large museum for Matryoshka dolls – traditional Russian nested toys. Inside the museum, there was a strange labyrinth. Its rooms and the labyrinth itself were squares and their walls were parallel to the north-south and east-west axes. Each chamber had four doors – one on each side. The entrance to the labyrinth was in the most northwestern room and the exit – in the most southeastern.
The Russian national team in ciphers prepared an interesting game for their opponents. In each room, they left a single empty Matryoshka doll with unique size. Everyone had to go through the labyrinth and collect as many toys as possible but under one condition. Every time someone picks a doll, he has to nest all the dolls he has into the new one. Of course, the contestants could decide whether to pick a Matryoshka (if it is bigger than the last one) or to continue to the next room. To make things even harder, the genius of the safes – Metr Pitrichev – had modified the doors so that from a room one can move only to the rooms to the south and to the east.
Peter, of course, was not such a master with the locks and could not deal with the modification. Instead, he wrote a program, which can find the best way to collect as many toys as possible. Can you do that, too? Write a program matr that calculates the maximum amount of Matryoshka dolls, which Peter the Hacker can collect for a given configuration of rooms.

Input Format

在標準輸入中,會先有一個數字N代表房間大小1<N<1000),接著下一行開始有一個N*N的表格(假設上下左右分別是北南西東方)。每個數字代表那個房間的娃娃大小。俄羅斯娃娃可以被裝進另一個的條件就是他的大小必須小於另一個要裝進他的娃娃。
娃娃大小會介於1到n2 之間,而且不重覆出現。

On the standard input you will get a single integer $N$ $(1 < N < 1000)$, followed by $N$ rows with $N$ numbers (one for each room). Every number describes the size of the toy inside the corresponding chamber. The rows are ordered from north to south (the first row is the most northern) and the columns are ordered from west to east (the first number on every row is the most western). A Matryoshka doll fits into another if it has smaller size than the second one. The sizes will be integer numbers in $[1, N2]$ and will not repeat.

Output Format

在標準輸出中,你只需要輸出一個數,代表最多可以收集到的娃娃個數。

On the standard output, you should print a single integer – the maximum amount of toys that Peter the Hacker can collect following the rules.

Sample Input

Sample Input #1:

3
9 4 1
6 5 7
2 3 8

Sample Input #2:

4
1 15 4 5
2 10 9 16
14 7 8 3
13 6 11 12

Sample Output

Sample Output #1:

4

Sample Output #2:

6

Hints

對不起,來不及翻譯了@@
大意就是說給你$N^ 2$個排成$N\times N$方陣的數字,每個數字都介於$1$和$N^ 2$之間而且沒有重複,請問從西北方(左上角)走到東南方(右下角),每次只能往東或往南,能夠蒐集到的最多俄羅斯娃娃的數量。(若「拾起」一個俄羅斯娃娃,那麼就必須把你手上所有的俄羅斯娃娃都塞進去才能繼續走)。

第一筆範例輸入:$9\rightarrow 4\rightarrow 5\rightarrow 7\rightarrow 8$,拿$4,5,7,8$。
第二筆範例輸入:$1\rightarrow 2\rightarrow 10\rightarrow 7\rightarrow 8\rightarrow 11\rightarrow 12$,拿$1,2,7,8,11,12$。

※2009/02/21 加入題目翻譯 by hallogameboy , 感謝 math120908

Problem Source

原TIOJ1266 / Bulgarian National Olympiad in Informatics 2008 Final (Prob A5)

Subtasks

For Testdata: 0 ~ 0, Score: 4
For Testdata: 1 ~ 1, Score: 4
For Testdata: 2 ~ 2, Score: 4
For Testdata: 3 ~ 3, Score: 4
For Testdata: 4 ~ 4, Score: 4
For Testdata: 5 ~ 5, Score: 4
For Testdata: 6 ~ 6, Score: 4
For Testdata: 7 ~ 7, Score: 4
For Testdata: 8 ~ 8, Score: 4
For Testdata: 9 ~ 9, Score: 4
For Testdata: 10 ~ 10, Score: 4
For Testdata: 11 ~ 11, Score: 4
For Testdata: 12 ~ 12, Score: 4
For Testdata: 13 ~ 13, Score: 4
For Testdata: 14 ~ 14, Score: 4
For Testdata: 15 ~ 15, Score: 4
For Testdata: 16 ~ 16, Score: 4
For Testdata: 17 ~ 17, Score: 4
For Testdata: 18 ~ 18, Score: 4
For Testdata: 19 ~ 19, Score: 4
For Testdata: 20 ~ 20, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 1500 131072
1 1500 131072
2 1500 131072
3 1500 131072
4 1500 131072
5 1500 131072
6 1500 131072
7 1500 131072
8 1500 131072
9 1500 131072
10 1500 131072
11 1500 131072
12 1500 131072
13 1500 131072
14 1500 131072
15 5900 131072
16 5900 131072
17 5900 131072
18 5900 131072
19 5900 131072
20 5900 131072