回分類題庫
h211: G.盤子分類
關鍵字: NPSC 2019 高中組初賽

測資點 : 3 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 17 Times / 15 Users | Submit : 31 Times / 19 Users | Accepted rate : 79%
題目加入時間 : 2020-05-14 13:41

Content: 简体中文

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

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

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

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

Input:

第一行有一個正整數 T,代表接下來有幾組測試資料。 

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

Output:

針對每組測試資料,請輸出一行包含一個整數,代表小 Y 最少需要耗費多少單位的體力才能把盤子分類放好。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
YYYYYY
YWWWWW
YW
WY
WW
YWWYW

Sample Output :

0
1
4

Hint :

Author :

NPSC 2019 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum