UVa 1631 密码锁

https://vjudge.net/problem/UVA-1631

题意：

有一个n位密码锁，每位都是0~9，可以循环旋转。每次可以让1~3个相邻数字同时往上或者往下转一格。输入初始状态和终止状态，问最少要转几次。

思路：

d[i][x][y][z]表示当前在复原第 i 位，当然前 i 位已经复原完毕，x代表第 i 位的数字，y代表第 i+1的数字， z代表第 i+2 的数字时的最少旋转次数。

每次我们需要复原第 i 位的数字，因为可以向上旋转和向下旋转2种方式，所以我们需要分别计算出向上和向下各需要旋转几下。接下来考虑 i+1 和 i+2 ，他们这两位可以跟着第 i 位一起旋转，也可以不旋转。所以我们需要枚举来讨论。但是，可以肯定的是，i+1 的旋转次数肯定是小于等于 i 的旋转次数的，同时，i+2 的旋转次数又是小于等于 i+1 的旋转次数的。

代码不难，就是一个记忆化搜索。

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn =  + ;

 const int INF = ;

 char s1[maxn], s2[maxn];

 int a[maxn], b[maxn];

 int d[maxn][][][];

 int len;

 int dp(int cur, int x, int y, int z )

 {

     if (cur >= len)  return ;

     int& ans = d[cur][x][y][z];

     if (ans!=-)    return ans;

     ans = INF;

     //向上旋转

     int t;

     if (x <= b[cur])    t = b[cur] - x;

     else                t = b[cur] +  - x;

     for (int j = ; j <= t;j++)

     for (int k = ; k <= j; k++)

         ans = min(ans, dp(cur + , (y + j) % , (z + k) % , a[cur+] ) + t);

     //向下旋转

     if (x >= b[cur])    t = x - b[cur];

     else                t=x +  - b[cur];

     for (int j = ; j <= t; j++)

     for (int k = ; k <= j; k++)

         ans = min(ans, dp(cur + , (y - j + ) % , (z - k +  ) % , a[cur+] )+t);

     return ans;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (cin >> s1 >> s2)

     {

         memset(d, -, sizeof(d));

         len = strlen(s1);

         for (int i = ; i < len; i++)

         {

             a[i] = s1[i] - '';

             b[i] = s2[i] - '';

         }

         a[len] = a[len + ] = b[len] = b[len + ] = ;

         cout << dp(, a[], a[],a[]) << endl;

     }

     return ;

 }