HDU 4433 locker（12年天津，DP）

题目：给出两个串，每次可以选择连续的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这个关系不能错

[cpp]
#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;
}

#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;
}

补充：软件开发 , C++ ,