题目大意是给定一个密码锁的初始状态和最终状态，每次可以转动连续的一或二或三个状态，问到最终状态最少需要转几次。
思路
DP
设d(i, x, y) 为 前i个字符已经匹配好，第i + 1的数字是x， 第i + 2的数字是y。则状态转移方程为
d(i, y + a, z + b) = min{d(i, y + a, z + b), d(i - 1, x, y) + step}
step为第i位匹配所需要的步数，a是转动i+1位的次数，b是转动i+2位的次数，注意b<=a<=step 因为我们每次转动要么转动3个要么转动两个，要么只
转动第i位的。同时再考虑正转和逆转。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1000 + 10; const int INF = 0x4f4f4f4f; char p[maxn], t[maxn]; int n; int d[maxn][20][20]; int solve(){ d[0][p[1] - '0'][p[2] - '0'] = 0; for(int i = 1; i <= n; ++i){ for(int x = 0; x < 10; ++x){ for(int y = 0; y < 10; ++y){ int step = (t[i] - x - '0' + 10) % 10; for(int a = 0; a <= step; ++a){ for(int b = 0; b <= a; ++b){ int & ans = d[i][(y + a) % 10][(p[i + 2] - '0' + b) % 10]; ans = min(ans, d[i - 1][x][y] + step); } } step = 10 - step; for(int a = 0; a <= step; ++a){ for(int b = 0; b <= a; ++b){ int & ans = d[i][(y - a + 10) % 10][(p[i + 2] - '0' - b + 10) % 10]; ans = min(ans, d[i - 1][x][y] + step); } } } } } return d[n][0][0]; } int main() { while(scanf("%s %s", p + 1, t + 1) == 2){ n = strlen(p + 1); p[n + 1] = p[n + 2] = '0'; t[n + 1] = t[n + 2] = '0'; for(int i = 0; i <= n; ++i) for(int j = 0; j < 10; ++j) for(int k = 0; k < 10; ++k) d[i][j][k] = INF; printf("%d\n", solve()); } return 0; }