a209. G. 盤子分類 - YUTEH ZeroJudge

內容

2019 網際網路程式設計全國大賽高中組初賽

小 Y 是個喜歡收集盤子的收藏家，他在家中收集了各式各樣的盤子，並且按照盤子的顏色分類，把每種顏色的盤子疊成一疊。

有一天，他發現他收集的盤子竟然被打亂了！原來是小 P 一時無聊，就把黃色和白色這兩疊盤子隨意交換。小 Y 無法忍受黃白夾雜的盤子疊成一疊，因此他決定要趕快把這兩種顏色的盤子分類放好（一疊全部都是黃色，一疊全部都是白色。至於哪一疊是黃色、哪一疊是白色對小 Y 來講並不重要）。

不幸的是，由於小 Y 家實在有太多盤子了，所以他找不到多餘的空間可以整理這些盤子

（因為一不小心可能會摔碎其他的盤子）。因此，他決定直接用這兩疊盤子的空間來把盤子分類。具體來說，小 Y 每次會選一個盤子，把它抽出來後並放到另一疊盤子的最上面，一直重複這樣的動作直到盤子分類好為止。但是要把盤子從一整疊盤子的中間抽出來就代表要暫時把上面所有的盤子抬起來，因此如果那個要抽出來的盤子上面有 x 個盤子，那抽出這個盤子會讓小 Y 耗費 x 單位的體力。而整個小 Y 分類盤子的過程所耗費的體力就是每一次動作所耗費的體力的加總。

小 Y 想要用最少的體力把盤子分類放好。但是他的數學不好，不太會解最優化問題。所以請你幫忙他計算出他最少需要耗費多少單位的體力才能把盤子分類放好。

輸入說明

輸入只有兩行，兩行各有一個僅以Y和W組成的字串，分別代表兩疊盤子中由上而下每個盤子的顏色，Y代表黃色、W代表白色。

兩疊盤子的盤子數量均介於1和20000之間（含）。

輸出說明

請輸出一行包含一個整數，代表小 Y 最少需要耗費多少單位的體力才能把盤子分類放好。

範例輸入

YYYYYY
YWWWWW
--------------------------------
YW
WY
--------------------------------
WW
YWWYW
--------------------------------

範例輸出

0
--------------------------------
1
--------------------------------
4
--------------------------------

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1M
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

標籤:

2019高中組初賽

出處:

NPSC [管理者：

zero (管理員)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」