学步园

题意:

给出密码做的现状和密码, 每次可以移动连续的最多3列, 向上或向下, 求将密码调出来所需要的最少步数.

思路:

首先应看出,恢复的过程中, 调每一位的时间顺序是不影响的, 不妨就从左到右一位位消除.

dp[ i ][ x ][ y ] 表示前 i 位已经消除为0, 且其后的两位为x,y时, 所需要的最小操作数.

每次可以旋转1~3位, 注意旋转3位时, 第三位和第二位的约束关系.[因此而wa了...]

和Wordstack那道题的"题解版"的思路相同, 用已知的状态去更新未知的状态.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int dp[MAXN][10][10], bit[MAXN], n;
char s[MAXN], t[MAXN];
int main()
{
    while(~scanf("%s %s",s,t))
    {
        n = strlen(s);
        for(int i=0;i<n;i++)
            bit[i+1] = (t[i]+10-s[i]) % 10;
        bit[n+1] = bit[n+2] = 0;
        memset(dp,0x3f,sizeof(dp));
        dp[0][bit[1]][bit[2]] = 0;
        for(int i=0;i<n;i++)
            for(int x=0;x<10;x++)
                for(int y=0;y<10;y++)
                    if(dp[i][x][y]!=INF)
                    {
                        dp[i+1][y][bit[i+3]]
                         = min(dp[i+1][y][bit[i+3]],
                               dp[i][x][y] + min(x,10-x));//1
                        for(int j=1;j<=x;j++)
                        {
                            dp[i+1][(y+10-j)%10][bit[i+3]]
                             = min(dp[i+1][(y+10-j)%10][bit[i+3]],
                                   dp[i][x][y] + x);//2
                            for(int k=1;k<=j;k++)
                                dp[i+1][(y+10-j)%10][(bit[i+3]+10-k)%10]
                                 = min(dp[i+1][(y+10-j)%10]
                                         [(bit[i+3]+10-k)%10],
                                       dp[i][x][y] + x);
                        }
                        for(int j=1;j<=10-x;j++)
                        {
                            dp[i+1][(y+j)%10][bit[i+3]]
                             = min(dp[i+1][(y+j)%10][bit[i+3]],
                                   dp[i][x][y] + 10-x);//2
                            for(int k=1;k<=j;k++)
                                dp[i+1][(y+j)%10][(bit[i+3]+k)%10]
                                 = min(dp[i+1][(y+j)%10][(bit[i+3]+k)%10],
                                       dp[i][x][y] + 10-x);
                        }
                    }
        printf("%d\n",dp[n][0][0]);
    }
}

话说...这是组队以来我做的第一道非水题.....对我而言的非水题吧......

DP还是比较有意思的, 要多多练习~ orz