首页 > 搜索 > BFS搜索 > HDU 4433- locker-动态规划-[解题报告]HOJ
2015
07-16

HDU 4433- locker-动态规划-[解题报告]HOJ

locker

问题描述 :

A password locker with N digits, each digit can be rotated to 0-9 circularly.
You can rotate 1-3 consecutive digits up or down in one step.
For examples:
567890 -> 567901 (by rotating the last 3 digits up)
000000 -> 000900 (by rotating the 4th digit down)
Given the current state and the secret password, what is the minimum amount of steps you have to rotate the locker in order to get from current state to the secret password?

输入:

Multiple (less than 50) cases, process to EOF.
For each case, two strings with equal length (≤ 1000) consists of only digits are given, representing the current state and the secret password, respectively.

输出:

Multiple (less than 50) cases, process to EOF.
For each case, two strings with equal length (≤ 1000) consists of only digits are given, representing the current state and the secret password, respectively.

样例输入:

111111 222222
896521 183995

样例输出:

2
12

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove

题目:给出两个串,每次可以选择连续的1-3个数字,进行同时加1或者同时减1,问最少经过多少次操作,将一个串转变为另外一个串

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

以前有类似的题目,BFS就可以了

不过这题的数据量太大,听说也有不少是搜索过的

我写了一个矬B的搜索,反正是挂了,没加什么优化

训练的时候,yobobobo的DP解法比较接近,可是最终貌似卡在后效性上?

dp[i][j][k]表示 前i个已经完全匹配,而这时候,第i+1个已经加了j位,第i+2位已经加了k

转移分为两步,枚举加,枚举减

注意如果第i位加了a,第i+1位加了b,第i+2位加了c,那么a>=b>=c这个关系不能错

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define inf 1<<20
#define N 1005
using namespace std;
char s1[N],s2[N];
int dp[N][10][10];
int main(){
    while(scanf("%s%s",s1,s2)!=EOF){
        int l=strlen(s1);
        for(int i=0;i<=l;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<l;i++)
            for(int j=0;j<10;j++)
                for(int k=0;k<10;k++){
                    int t=(s2[i]-s1[i]-j+20)%10;
                    for(int a=0;a<=t;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]+t);
                    t=(10-t)%10;
                    for(int a=0;a<=t;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]+t);
                }
        printf("%d\n",dp[l][0][0]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/8124726