Eileen has a big luggage and she would pick a lot of things in the luggage every time when A-SOUL goes out for a show. However, if there are too many things in the luggage, the 4-digit password lock on the luggage will be hard to rotate.0900 in one step because the rotated digits are consecutive, but she can't rotate. 0101 in one step. Since she has little strength, she wants to rotate the lock as few times as possible.. As a fan of A-SOUL, you are asked to help Eileen find out the optimal plan to unlock but you only need to tell Eileen how many times she has to rotate.
Eileen has a big luggage and she would pick a lot of things in the luggage every time when A-SOUL goes out for a show. However, if there are too many things in the luggage, the 4-digit password lock on the luggage will be hard to rotate. The state of lock is the four digits on the lock. In one step, she can choose consecutive digits to rotate up by one simultaneously or down by one simultaneously. For example, she can rotate texttt{0000} 0000 to texttt{0111} 0111 or texttt{0900} 0900 in one step because the rotated digits are consecutive, but she can't rotate texttt{0000} 0000 to texttt{0101} 0101 in one step. Since she has little strength, she wants to rotate the lock as few times as possible. Now the lock is at state a_0a_1a_2a_3 a a 1 a 2 a 3 and the password is b_0b_1b_2b_3 b b 1 b 2 b 3 . As a fan of A-SOUL, you are asked to help Eileen find out the optimal plan to unlock but you only need to tell Eileen how many times she has to rotate.
![HBC230862[HAOI2009]逆序对数列,动态规划Luggage Lock题解
-第1张图片-东莞河马信息技术](https://www.xxstcz.com/zb_users/upload/2023/11/20231111140602169968276279610.jpeg "HBC230862[HAOI2009]逆序对数列,动态规划Luggage Lock题解
-第1张图片-东莞河马信息技术")
