回分類題庫
z123: E.撿石頭
關鍵字: 2001 NPSC 國中組 初賽

測資點 : 1 | Time Limit : 1000 ms | Memory Limit : 128000 KB
Accepted : 1 Times / 1 Users | Submit : 12 Times / 4 Users | Accepted rate : 25%
題目加入時間 : 2021-03-29 21:06

Content: 简体中文

  有一個富翁想為女兒找個好歸宿,他想出了一個方法,把全村的壯丁都集中在一起比賽,每個人分配到一排石頭,請壯丁們從自己那一排中盡量撿出最大的一塊。很多人一路丟丟撿撿,不時回首顧盼,只有一位青年,大略的看中一塊大石頭後便一路走到終點。富翁認為他能夠珍惜所有,在娶了女兒之後必定能夠專一,而不會像其他人一般丟丟撿撿,對自己所得一直無法滿意,便選了他做東床快婿。

  這回富翁又要嫁女兒了,一張撿石頭比賽的公告又貼在村口。村民們有了上次經驗,早就摩拳擦掌,準備撿一塊大石頭就走到終點。但一到比賽會場才發現規則早已變更如下:

1.每個人還是只准撿自己那一排的石頭。
2.只准前進不准後退。
3.可以撿不只一塊石頭,但後來撿的必須比之前已經撿起的都要大才行。
4.盡量撿最多塊石頭。

  身為一個為富翁寫程式的長工,你決定要好好一展長才,不再讓人看扁。由於近水樓臺,你已經偷偷地知道每塊石頭的大小關係,現在你的目標是寫出一個程式能撿到最多塊石頭。

Input:

  輸入會由一個整數N開始,表示測試資料的筆數。每一筆測試資料會由一個整數m開始,表示石頭的數目,接下來是m行,每一行有一個整數(有可能為負數,你的程式要能處理),表示石頭的大小關係,數字越大石頭也越大。(1<=m<=100000)。

Output:

  每一筆測試資料印出一個數字,表示最多可以拿的石頭數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
輸入範例:
2
5
1
2
3
4
5
5
5
4
3
2
1

Sample Output :

輸出範例:
5
1

Hint :

Author :

2001 NPSC 國中組 初賽 (管理員:wubaie)

  Solve it!   Status Forum