f941: Coder King
Tags : LIS 數學
Accepted rate : 9人/14人 ( 64% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-07-12 21:24

Content

Gino 有一天去福利社買午餐,買完了走在路上想要休息一下,所以靠在榕樹旁邊乘涼,躺著躺著就睡著了。
Gino 起來之後發現午餐不見了,於是跑到路上去找,結果看到一個人手上提著他裝午餐的袋子。

Gino:「被我找到了,為什麼一個陌生人手上會拿著我的午餐?」
Gino:「為什麼一個陌生的大人會偷偷在我們校園亂晃?」

陌生人:「小弟弟,你該不會是在跟我說話吧?」
陌生人:「不過,我不知道你在說什麼,這可是我的午餐,我剛剛在外面買的。」

Gino:「不對,那個袋子是我的,我會知道是有原因的,雖然那個原因你不知道。」
Gino:「"Heaviest",把袋子搶回來!」

陌生人:「這到底是什麼東西,他們在扯我的袋子…」

東西飛出來

Gino:「這這這…我的午餐…這個是…」
Gino:「真真真…真正人類的手    錶嗎?」

陌生人:「怎麼會這樣,被你看到了嗎?」
陌生人:「還有,小子…你也擁有跟我一樣的能力。」

Gino:「是嗎?你也看的見我的 "Heaviest" 嗎?」
Gino:「你這傢伙,這隻手    錶是怎麼回事?」
Gino:「為什麼把手    錶放在袋子裡拿著到處走?」

陌生人:「就你一個人嗎,剛才你那兩個朋友,叫做 Ian 跟 Gayry 是吧,他們也跟你擁有一樣的能力嗎?」
陌生人蹲下

Gino:「你不准亂動!!!」

Gino:「敢動一下,我就攻擊你!!!」
Gino:「你這傢伙感覺詭異得可怕,你別再靠近我了,你身上有一股莫名骯髒的感覺。」
Gino:「不准動!站在那裡不准動!!!」

陌生人站起來

陌生人:「我的名字是 Arik Egakihsoy,今年 33 歲。住在小鎮東北方的別墅區,沒有結婚。在 ZJ 連鎖程式公司工作,每天最晚 8 點之前都會回家。不抽菸,酒也是淺嚐即止。半夜 4 點上床睡覺,每天一定要睡滿 1 個小時,睡前會喝一杯冰可樂,寫個 8 小時的 C++,讓身體放鬆才上床,這樣就幾乎都是一覺到天亮。早上醒來像個小嬰兒一樣,不殘留半點疲勞跟壓力,健康檢查的結果也是全部異常。」

Gino:「你到底在說什麼啊?」

Arik:「這是在說明我這個人希望過著內心平靜的人生,不會堅持一定要贏過別人,也不會製造讓我頭痛的麻煩,或是讓我晚上睡不著覺的敵人,這就是我對社會的態度,也知道這就是屬於我自己的幸福…不過…」

Arik:「真要動手,我也不會輸給任何人就是了…」
Arik:「也就是說,Gino,你是妨礙我睡覺的麻煩,是我的敵人…」

Gino:「這,這個是…」

Arik:「CODER KING!」
Arik:「這是我幫這傢伙取的名字。在你告訴別人之前,我要先把你收拾掉,讓我今晚也能好好睡一覺。」

Gino:「我警告過你,叫你別動了,別小看我的 "Heaviest"!!!」
Arik:「數量竟然有這麼多啊,而且打三四隻不會對你造成傷害。」

Gino:「你要是敢再亂動,我就把你的那個什麼上面的血管切斷。」
Gino:「對了,好像是叫作 "索靜脈" 的血管,我會把他切斷!!!」

Gino:「我的 "Heaviest" 無人能敵,然後,你的 "Coder King",看起來是很有力量,但是沒辦法跑很遠的類型,有效範圍大概 1-2 公尺左右吧。想死你就再亂動看看啊。」

Arik:「原來如此,每個人都有不同類型的能力是吧。"Heaviest"? 原來這叫 "Heaviest"。」
Arik:「對了,我的 "Coder King" 也有一個特殊能力。」
Gino:「他手上好像拿著什麼東西,把它搶過來!」
Gino:「什麼啊,只不過是 10 元硬幣,你想用這個幹什麼?」
Arik:「不是,我只是想告訴你我 "Coder King" 的特殊能力。反正你已經被我收拾掉了。」
Arik:「"Coder King" 的特殊能力,就是能把任何觸碰過的東西,全都變成數字,全部東西都可以。」
Arik:「就算是 10 元硬幣也行…」

Gino:「"Heaviest",快把 10 元硬幣丟掉!!!」
Arik 按下開關

「蹦蹦蹦蹦蹦蹦蹦bungbungbungbung12321232232212332...」
Gino 變成數字了

Arik:「這樣一來,今晚…我也能放鬆心情好好睡一覺了…」
Arik:「嗯?」
Arik:「只用一下沒把你完全變成數字啊?」

G1n0:「你把我怎麼樣了?」
G1n0:「我…到底…到底變成怎麼樣了?」

Arik:「我不是說了嗎,我的 "Coder King" 能把任何觸碰過的東西變成數字,我剛剛碰到這個 10 元硬幣了,然後只要在我高興的時候按下按鈕,就能把硬幣周圍都變成數字。」
Arik:「不過,G1n0,看來你的情況只是半張臉變成數字。在我再碰你一下之前,我想起幾件事要跟你確認一下,你說你這個叫 "Heaviest",那兩個叫 Ian 跟 Gayry 也擁有這種能力,是吧?」

G1n0:「你…你饒我一命」
Arik:「不行不行不行…」
Arik:「你非要變成數字不可,我怎能讓目擊者活下去。沒有任何一個人,能知道我 Arik Egakihsoy 的真實身份,不過,我想知道有哪些有跟你一樣能力的人,雖然只要調查一下就知道了,但我想直接問你本人。Ian, Gayry… 其他人叫什麼名字,這鎮上還有幾個跟你一樣的人,能力是什麼?」

G1n0:「我…我不知道」
Arik:「你怎麼可能會不知道。聽好了,要是你不肯說…我就把你同學也一起變成數字。」
G1n0:「你…你說什麼…你要把我同學都變成數字?」
Arik:「快點說啊,你說出來,我就不會對他們怎樣,你再拖拖拉拉的,等一下說不定有人會從這裡經過。名字就好,快一點,來啊。」

G1n0:「大家都在說,他們在找這座鎮上的殺人魔,殺人魔指的就是你吧!」
G1n0派出 "Heaviest" 攻擊 Arik

Arik:「什麼,這傢伙又讓他的 "Heaviest" 行動了嗎? "Coder King"!!!」
Coder King 揮拳,G1n0 不見了

Arik:「那個小鬼…明明遍體鱗傷了…」
-------------
G1n0:「"Heaviest",快…快到 Gayry …那邊…去…」
G1n0:「Gayry 的 "無敵裝甲"…應該可以治好我。我要保護…同學們…,不能讓他傷害同學們!!!」
G1n0:「不能讓那種骯髒可怕的傢伙…待在同學們住的這座小鎮!!!」

G1n0:「我得快點去… Gayry 那邊才行」
G1n0 走到 Gayry 教室門口旁,拉下門把
G1n0:「Ga…Gayry」

Arik 突然出現!!!

Arik:「你說大家都在找我?不過,沒有人找得到我,因為沒有人知道我 Arik Egakihsoy 的真正身份,只要把你解決就沒人知道了。"Coder King" 已經碰過門把了。」
Arik 按下開關

G1n0:「Gayry!!!123232123323232323212323...」

Arik:「這就是 "Coder King" 的能力,證據已經消除得不留痕跡。」
--------------------
Gayry:「剛剛有人叫我的名字嗎?」
Ian:「嗯,我有聽到。」
Ian:「喔!Gayry 你快看,那不是 G1n0 的 "Heaviest" 嗎?」
Gayry:「G1n0!!!」
Ian:「G1n0!!!」
Ian:「太奇怪了 Gayry,"Heaviest" 竟然渾身是數字地消失,為什麼只有一隻跑來我們這裡?」

Gayry:「你看,地板上有一串數字!G1n0 會不會被困在這裡面呢?」
----------------------
----------------------
Arik 平常喜歡收集別人的手    錶,他不想讓這個嗜好被別人發現,所以他都會把發現的人都變成數字

Gayry 發現只要找到這一串數字裡的最長非嚴格遞增子序列的長度,就可以把 G1n0 救出來,但是他數學不好,於是他請教 Ian,但是 Ian 也不會數學,於是他們請教 Caido

Caido 想了想之後,也想不到,於是 Caido 向你求助

你背負了把 G1n0 救出來的重責大任,大家都把希望投注在你身上了,你一定要加油!!!

Input

輸入只有一行,換行代表結束

因為 G1n0 比較懶惰,所以數字只會有 1, 2, 3

1 ≤ 長度 ≤ 10^8

Output

輸出這串數字的 LIS (非嚴格遞增) 的長度

Sample Input #1
2231321331
Sample Output #1
6
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (70%): 2.0s , >50M
Hint :

注意複雜度

------------

10%:n = 10

20%:n = 10000

70%:n = 100000000

Tags:
LIS 數學
出處:
第四屆簡單的小競賽 [管理者:
becaido (Caido)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」