题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4433
题目大意：给你一连串密码，（密码是0-》9循环转动），求最少的步骤到达目标数码。
算法思路：这个题一看就觉得要用dp思想，就是方程不好想，抓住题目给的可以连续拨动1-3密码，我的dp[i][j][k]表示第i个数字为j,第i+1个数字为k，i及以后到达目标所有的最少步骤。然后记忆化搜。
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;int dp[1050][10][10]; char in[1050],out[1050]; int len;int dfs(int cur,int num1,int num2) {if(cur == len+1) return 0;if(dp[cur][num1][num2] != -1) return dp[cur][num1][num2];int ret = 0x3f3f3f3f;int outnum = out[cur]-'0';int upstep = (outnum+10-num1)%10;int downstep = (num1+10-outnum)%10;if(cur == len){return min(upstep,downstep); //没有这句，是一直wa的原因，主要是dp下标必须为正，但我不知道为啥不会报错 }//只拨动cur对应的密码：ret = min(ret,dfs(cur+1,num2,in[cur+2]-'0') + min(upstep,downstep));if(cur < len) {for(int i=1; i<=upstep; i++)ret = min(ret,dfs(cur+1,(num2+i+10)%10,in[cur+2]-'0')+ upstep );for(int i=1; i<=downstep; i++)ret = min(ret,dfs(cur+1,(num2-i+10)%10,in[cur+2]-'0')+ downstep );}if(cur < len - 1){for(int i=1; i<=upstep; i++)for(int j=1; j<=i; j++)ret = min(ret,dfs(cur+1,(num2+i+10)%10,((in[cur+2]-'0')+j+10)%10) + upstep );for(int i=1; i<=downstep; i++)for(int j=1; j<=i; j++)ret = min(ret,dfs(cur+1,(num2-i+10)%10,((in[cur+2]-'0')-j+10)%10) + downstep );}dp[cur][num1][num2] = ret;return ret; }int main() {while(scanf("%s %s",in+1,out+1) == 2){len = strlen(in+1);memset(dp,-1,sizeof(dp));int ans = dfs(1,in[1]-'0',in[2]-'0');printf("%d\n",ans);} }
