#29351:


AtwoodYen (帥剛剛)

學校 : 不指定學校
編號 : 110732
來源 : [59.120.140.251]
最後登入時間 :
2024-11-20 10:59:56
d609. Necklace -- USACO | From: [51.15.124.20] | 發表日期 : 2022-02-17 17:12

項鍊 wwbrbwrwrb

變成二條接在一起 wwbrbwrwrb wwbrbwrwrb

用DP算出

   wwbrbwrwrbwwbrbwrwrb

r  12010123401201012340

b 12301201012340120101  

找一個顏色就好,我們找r來做換顏色(斷點),也就是此時為r>0,但接下來r=0的地方

   wwbrbwrwrbwwbrbwrwrb

r  12010123401201012340

由此斷點往後找最長b數量,相加

   wwbrbwrwrbwwbrbwrwrb

b 23101200012340120101

得到4+4=8

唯要小心若換顏色(斷點)為w時,表示共用w,則最後算出長度要減1

 
ZeroJudge Forum