h558. pB. 打鍵盤(keyboard) - 高中生程式解題系統

內容

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

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

限制:

$1 \leq n \leq 10^{4}$

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

輸入說明

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

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

輸出說明

輸出最小時間。

範例輸入 #1

1
N

範例輸出 #1

範例輸入 #2

3
ALG

範例輸出 #2

範例輸入 #3

4
ALFQ

範例輸出 #3

測資資訊：

記憶體限制： 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

提示：

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

題目和測資來源:twpca

另外抱歉這裡沒有分subtasks。

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

標籤:

DP 動態規劃

出處:

TOI入營考 2022 [管理者： rickysucksatcode@gmail.com

r1cky (hehe) ]

編號	身分	題目	主題	人氣	發表日期
34836	mushroom.cs9 ... (mushroom)	h558		506	2023-04-19 22:23