题意：

有一个n（n≤1000）位密码锁，每位都是0～9，可以循环旋转。每次让1～3个相邻数字同时往上或者往下转一格，567890->567901（最后3位向上）。输入初始状态和终止状态（长度不超过1000），问最少要转几次。

这道题刚开始看有点蒙，不知道应该如何转密码锁上面的格，然后通过经验能够感觉出来最优的转动方案是可以按照

从左到右的顺序来移动到正确的位置的，这样我们将无序的转动变成了有序的转动，自然问题就简化了许多，

然后通过观察题意(每次让1～3个相邻数字同时往上或者往下转一格)，我发现1-3个相邻的数字说明了如果按照从左到右的

顺序进行转动后那么可以仅仅影响前面或后面1-3个格子的，然后发现影响后面的格子会更好写程序，所以下面是状态与转移方程：

  d(i,j,k,p)表示前i-1个已经配对，其中i、i+1、i+2分别对应j、k、p还需要最少波动次数

  状态转移方程:其中第i个一定要拨动使之配对，其余的i+1、i+2可以随着i的拨动进行改变(也可以不改变)，可以往上下拨。

  最后答案为d(0,a[0],a[1],a[2])

这需要使用记忆化搜索求解，刚开始我拨动的时候犯了一个错误，如果i拨动x次，那么i+1、i+2也一定拨动x次，或者仅仅i+1拨动x次，

这样其实是错误的(想一想，为什么)，后面拨动的次数是任意的(但需要保证小于前面拨动次数)，下面是代码：

// UVa 1631 /*  d(i,j,k,p)表示前i-1个已经配对，其中i、i+1、i+2分别对应j、k、p还需要最少波动次数  状态转移方程:其中第i个一定要拨动使之配对，其余的i+1、i+2可以随着i的拨动进行改变(也可以不改变)，可以往上下拨。  最后答案为d(0,a[0],a[1],a[2])*/#include 
     
       #include 
      
        #include 
       
        using namespace std; const int maxn = 1000 + 10; const int INF = 1000000003; char s[maxn], s2[maxn];int len, a[maxn], b[maxn]; int d[maxn][11][11][11]; int dp(int cur, int x, int y, int z) {   if (cur >= len) return 0;     int& ans = d[cur][x][y][z];   if (ans >= 0) return ans;     ans = INF;  int down = (b[cur]+10-x)%10, up = (x+10-b[cur])%10;  for (int i = 0; i <= down; ++i)     for (int j = 0; j <= i; ++j)       ans = min(ans, dp(cur+1,(y+i)%10,(z+j)%10,a[cur+3])+down);  for (int i = 0; i <= up; ++i)     for (int j = 0; j <= i; ++j)       ans = min(ans, dp(cur+1,(y+10-i)%10,(z+10-j)%10,a[cur+3])+up);  return ans; }int main() {   while (scanf("%s%s", s, s2) == 2) {      len = strlen(s);       for (int i = 0; i < len; ++i) a[i] = s[i] - '0';       for (int i = 0; i < len; ++i) b[i] = s2[i] - '0';      a[len] = a[len+1] = a[len+2] = b[len] = b[len+1] = b[len+2] = 0;         memset(d, -1, sizeof(d));       printf("%d\n", dp(0,a[0],a[1],a[2]));  }  return 0;}