学步园

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4433

题目大意：就是给你一个序列，相当于一个可以转的那种密码锁的初始状态，0往下转是9，9往上转是0，现在你要把它转成一个指定的序列，每次可以转动连续的1~3个数字，问你最小的操作数。

思路：DP题这是很清楚的，可是状态有点不好设计。设d[ i ][ x ][ y ] 表示前 i 个已经转好，然后 i+1 转成 x，i+2 转成 y 的最小步数，然后这个状态只能由 i-1 转换过来（这个自己想想就知道了），那么把 from[ i ] 转成 to[ i ] ，可能往上转，可能往下，然后这样就把 i 配对好了，i 可能带动 i+1 和 i+2,，i+1 的那里是y，i+2 那里是 from[ i+2 ]，设 i 匹配的步数为 p，那么p >=  i+1 那里带动的步数 >= i+2 那里带动的步数，然后枚举这些步数，就可以完成状态转移，具体参见代码吧！

2012 天津现场的一道题，当时记得很清楚，这道题一直卡到死。。。 现在回过头来再做，说实话，我也是看了解题报告才A了的，自己仍旧没想出来。。  今天做的时候的思路包括当时现场赛时的思路，就是有一个地方一直没弄清楚。我都只想到了一维d[ i ]，用来表示前 i 个的最小步数，然后转1~3个进行转移，但是第二个样例怎么也弄不出来，其实这里有一个漏洞，就是当我们旋转第 i 个的时候，i+1、i+2 那里是有可能也顺手去转动一下的，所以说一维的这样设计算出来肯定是多的。相当于是有了后效性，由于第
i 个它只能影响后两个，所以再增设两维，用于表示顺手带动的后面两个的状态，这样就消除了后效性，唉，关键就是这里啊！

真是一道不错的题目啊！

代码如下：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

const int INF = 0x0fffffff;

const int MAXN = 1111;

char from[MAXN],to[MAXN];

int d[MAXN][11][11];

int main()
{
    from[0] = to[0] = 0;
    while(~scanf("%s%s",from+1,to+1))
    {
        int len = strlen(from+1);
        for(int i = 1;i <= len;i++)
        {
            from[i] = from[i]-'0';
            to[i] = to[i]-'0';
        }
        from[len+1] = to[len+1] = from[len+2] = to[len+2] = 0;
        for(int i = 0;i <= len;i++)
            for(int j = 0;j < 10;j++)
                for(int k = 0;k < 10;k++)
                    d[i][j][k] = INF;
        d[0][from[1]][from[2]] = 0;
        for(int i = 0;i < len;i++)
        {
            for(int x = 0;x < 10;x++)
                for(int y = 0;y < 10;y++)
                {
                    if(d[i][x][y] >= INF) continue;
                    int down = (x-to[i+1]+10)%10;
                    for(int j = 0;j <= down;j++)
                        for(int k = 0;k <= j;k++)
                        {
                            d[i+1][(y-j+10)%10][(from[i+3]-k+10)%10] = min(d[i][x][y]+down,d[i+1][(y-j+10)%10][(from[i+3]-k+10)%10]);
                        }

                    int up = (to[i+1]-x+10)%10;
                    for(int j = 0;j <= up;j++)
                        for(int k = 0;k <= j;k++)
                        {
                            d[i+1][(y+j)%10][(from[i+3]+k)%10] = min(d[i][x][y]+up,d[i+1][(y+j)%10][(from[i+3]+k)%10]);
                        }
                }
        }
        printf("%d\n",d[len][0][0]);
    }
    return 0;
}