h558. pB. 打鍵盤(keyboard)
Tags : DP 動態規劃
Accepted rate : 51人/66人 ( 77% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-08 21:52

Content

完整題目:https://drive.google.com/file/d/1RSq17g00V-ygkC8x37iLhtNteoqLAwZg/view?usp=sharing

給你一個 qwert 英文鍵盤,然後有個人只會用兩隻食指打字,起始位置是左手在F,右手在J,手指可以在鍵盤上移動,但每次只能選擇一隻手往左、右、右上、右下、左上、左下移動一格,每次一隻手的移動耗時一秒。給你一長度 $n$ 的字串 $S$,問說打完至少要多久。(打字不耗時間,只有移動會花時間)

 

 

限制:

$1 \leq n \leq 10^4$

字串 $S$ 由英文大寫字母組成。

Input

第一行一個數 $n$ ,代表字串長度

接著一行有一長度為 $n$ 的字串 $S$, $S$ 由英文大寫字母組成。

Output

輸出最小時間。

Sample Input #1
1
N
Sample Output #1
1
Sample Input #2
3
ALG
Sample Output #2
9
Sample Input #3
4
ALFQ
Sample Output #3
11
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
Hint :

舉例來說,若文章僅有 N 一個字母,使用左手食指從 F 移動至 N,選擇 F → C → V → B → N 的移動路線所需的時間為 4 單位,而選擇 F → G → H → N 所需的時間為 3 單位。耗時最短的移動路線為使用右手食指,直接由 J 移動至 N,所需的時間僅為 1 單位,故答案為 1。

 

題目和測資來源:twpca

另外抱歉這裡沒有分subtasks。

如果題目有問題歡迎來信詢問!

Tags:
DP 動態規劃
出處:
TOI入營考2022 [管理者: r1cky (hehe) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
34836 mushroom.cs9 ... (mushroom) h558
題解
276 2023-04-19 22:23