#P1651. 密码锁

密码锁

提示信息:

密码锁:由n 个从左到右并排的圆环组成,每个圆环上都有10 个数字(0~9),蓝色框内为密码显示区,每个圆环在密码显示区只能显示一个数字,如图所示。可以拨动圆环,来改变密码显示区显示的数字。 当密码显示区的数字与密码一致时,密码锁就会被打开。 image

题目描述

有一个由n 个圆环组成的密码锁,和一个n 位的密码S(S 由1~9 中的数字(包含1和9)组成)。每次操作只能选择一个或位置连续的多个圆环拨动,当S 中的字符从左到右依次显示在密码显示区时,密码锁会被打开。 已知每个圆环在密码显示区初始数字都为0,请计算出最少需要操作多少次,才能打开密码锁。 注意

1、如果选择了其中一个圆环,可将该圆环中任意一个数字拨动到密码显示区,表示1 次操作; 例如:将第3 个圆环拨动到数字4,表示1 次操作:

image

2、如果选择了位置连续的多个圆环,只能将这些圆环拨动成同一个数字,显示在密码显示区,表示1 次操作。 例如:将连续的第2 个到第3 个圆环都拨动到数字5,表示1 次操作:

image

例如: n = 5,S = "12321";分别表示5 个圆环组成的密码锁和密码12321;将5 位密码1、2、3、2、1 从左到右依次显示在密码显示区,以下是操作最少次数的方案: 第一次操作,将5 个初始状态为0 的圆环全部拨动到数字1:

image

第二次操作,将第2 个到第4 个圆环全部拨动到数字2:

image

第三次操作,将第3 个圆环拨动到数字3:

image

最少需要操作3 次,才能打开密码锁。

输入格式

第一行输入一个整数n1n100n(1≤n≤100),表示组成的密码锁的圆环数及密码的位数 第二行输入一个长度为nn 的字符串SSSS191-9 中的数字(包含1199)组成,表示密码

输出格式

输出一个整数,表示最少需要操作多少次,才能打开密码锁

5
12321
3