HDU-4433

2018-03-04

题目链接

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

题目大意

有一把六位数字的密码锁，一次可以移动1/2/3位，向上移动一位或向下移动一位。给定现在的状态和密码的状态，问最少操作多少。

思想

这是一个动归，但是状态比较难描述。
我们记录dp[i][j][k]为前i位已经OK，第i+1位增加了j，第i+2位增加了k时，已经走了dp[i][j][k]步。
目前我们假设前i位已经OK，第i+1位增加了j，那么现在的i+1位变成正确的移动的步数为s2[i]-s1[i]-j。应该考虑up和down两个操作。
应该注意的是，第i位的操作数>=第i+1位的操作数>=第i+2位的操作数

代码

HDU-4433

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXL 1010
#define INF 1<<31-1
char ss[MAXL],st[MAXL];
int dp[MAXL][10][10];
int main()
{
    while (~scanf("%s%s",ss,st))
    {
        int len=strlen(ss);
        for (int i=0;i<=len;i++)
            for (int j=0;j<10;j++)
                for (int k=0;k<10;k++)
                    dp[i][j][k]=INF;
        dp[0][0][0]=0;
        for (int i=0;i<len;i++)
            for (int j=0;j<10;j++)
                for (int k=0;k<10;k++)
                {
                    int steps=(st[i]-ss[i]-j+20)%10;
                    for (int a=0;a<=steps;a++)
                        for (int b=0;b<=a;b++)
                            dp[i+1][(k+a)%10][b]=min(dp[i+1][(k+a)%10][b],dp[i][j][k]+steps);
                    steps=(10-steps)%10;
                    for (int a=0;a<=steps;a++)
                        for (int b=0;b<=a;b++)
                            dp[i+1][(k-a+10)%10][(10-b)%10]=min(dp[i+1][(k-a+10)%10][(10-b)%10],dp[i][j][k]+steps);
                }
        printf("%d\n",dp[len][0][0]);
    }
    return 0;
}

后记

很多DP都是看了能看懂但自己想不到。继续练习把。