在这里插入图片描述
UVA1631
定义：$dp[i][x][y][z]$为达到第$i$个数字之前已经解锁，第$i$个数为$x$，第$i+1$个数为$y$，第$i+2$个数为$z$的状态最少需要转动几下。
详见注释
AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
constexpr static int inf = 0x3f3f3f3f;
char Start[1002], End[1002];
int dp[1001][10][10][10];
int Len;
int DP(int Cur,int x,int y,int z) {
	if (Cur >= Len) {
		return 0;
	}
	int& Ans = dp[Cur][x][y][z];
	if (Ans != inf) {
		return Ans;
	}
	//还需向上转动几次才能使第Cur位解锁
	int&& Upper = (End[Cur] - x + 10) % 10;
	//在向上转Upper次第Cur位时，枚举所有的Cur+1，Cur+2位的可能
	for (int i = 0; i <= Upper; ++i) {
		for (int j = 0; j <= i; ++j) {
			Ans = min(Ans, DP(Cur + 1, (y + i) % 10, (z + j) % 10, Start[Cur + 3]) + Upper);
		}
	}
	//枚举向下转
	int&& Downer = (x - End[Cur] + 10) % 10;
	for (int i = 0; i <= Downer; ++i) {
		for (int j = 0; j <= i; ++j) {
			Ans = min(Ans, DP(Cur + 1, (y - i + 10) % 10, (z - j + 10) % 10, Start[Cur + 3]) + Downer);
		}
	}
	return Ans;
}
int main() {
	while (scanf("%s%s", Start, End) != EOF) {
		Len = strlen(Start);
		memset(dp, 0x3f, sizeof(dp));
		for (int i = 0; i < Len; ++i) {
			Start[i] -= '0';
			End[i] -= '0';
		}
		//令最后一位+1，最后一位+2相同，代表往后加两位已经转好的，方便枚举
		Start[Len] = Start[Len + 1] = End[Len] = End[Len + 1] = 0;
		cout << DP(0, Start[0], Start[1], Start[2]) << endl;
	}
	return 0;
}