[情報] Google Code Jam 2008 第一題解法

[bleed1979 (十三)]

Google Code Jam 2008　第一題

前面的宇宙會被擠壓的廢話就不多說了

這題的大意是在N組測資內, 有S個搜尋引擎要依序搜索Q個字

第一個選定的引擎不列入計算(count=0)

開始搜索後, 如果碰到的字和引擎的名字是相同的話

可以換引擎繼續搜索

求依序搜索完所有的字後, 所換引擎次數最少為多少

解法：

依次建立每個引擎不包括相同字的起點和終點

然後找終點最遠的引擎來更換


範例：

5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol

起點(從1開始算) 終點
Yeehaw
3 10

NSM
1 5
7 7
9 10

Dont ask
1 8
10 10

B9
1 3
5 6
8 10

Googol
1 2
4 4
6 9

開始跑：
從1開始跑, 有4個引擎都有1, 但Dont ask終點到8為最大, 所以一開始選Dont ask
再來從9開始跑, 包含9的有Yeehaw, NSM, B9　因為都到10　所以任選一個皆可
而10就是case的終點
所以換的次數最少為1次


還有5小時　有報名的可以參考看看


Bleed

--
ACM's PARADISE

http://bleed1979.myweb.hinet.net/


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.16.70
→ poga:我是直接從頭開始跑，判斷哪邊需要switch就好了
→ poga:畢竟輸出不需要包含用哪個engine
推 powertodream:我在想 search從頭掃到尾, 一直很greedy
→ powertodream:engine 五個都出現表示要換, 這樣會有問題嗎@@?y
推 netsphere:我也是用 greedy mathod
推 ledia:greedy 的基本題呀, 下一題也是
推 Romulus:greedy is ok
推 redray:我比較想知道第三題怎麼解..
推 Frozenmouse:我比較想知道第二題怎麼解..
推 hcldesmond:greedy +1
推 sasbluesea:greedy +1
推 windows2k:我用DP來解 XD, 果真變遲鈍了
推 Frozenmouse:樓上(握)  當下不知怎麼不敢用greedy...orz
推 Romulus:第二題就表全部建起來event-driven就好了