hdu 4433 Locker dp

locker Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1827    Accepted Submission(s): 833 Problem Description 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?   Input 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.   Output For each case, output one integer, the minimum amount of steps from the current state to the secret password.   Sample Input 111111 222222 896521 183995   Sample Output 2 12   Source 2012 Asia Tianjin Regional Contest   Recommend

zhoujiaqi2010   |   We have carefully selected several similar problems for you:  5842 5841 5840 5839 5838 

代码//

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 1008 #define inf 1<<20//表示2^的20次方 using namespace std; int dp[2][maxn][maxn]; //dp[i][j][k]表示前i个已经转好，第i+1个向上转了j次，第i+2个向上转了k次的最小操作次数；这里的i没必要表示，可以用滚动数组。 char s1[maxn], s2[maxn]; int main() { int i, j, l, k, a, b; while (~scanf("%s%s", s1, s2)) { l = strlen(s1); for(i = 0; i < 10; i++) for(j = 0; j < 10; j++) dp[0][i][j] = inf; int v = 0, t; dp[0][0][0] = 0; for(i = 0; i < l; i++) {//枚举这l个数，每次能把第i位转好，第i+1位和第i+2位分别转了0到9的最小值求出 for(j = 0; j < 10; j++) for(k = 0; k < 10; k++) dp[v^1][j][k] = inf;// 初始滚动数组为最大； for(j = 0; j < 10; j++) for(k = 0; k < 10; k++) {//第i+1位和第i+2位分别转了j次和k次； t = (20+s2[i]-s1[i]-j)%10;//第i+1此时转成了是s[i]+j(<20),t表示要向上转t次才能转好 for(a = 0; a <= t; a++)//第i+1位可以转0到t次 for(b = 0; b <= a; b++)// 第i+2位可以转0到a次；；--总之满足 t>=a>=b; dp[v^1][(k+a)%10][b] = min(dp[v^1][(k+a)%10][b], dp[v][j][k]+t);//这里要进位； t = (10-t)%10;//向下转，不多解释 for(a = 0; a <= t; a++) for(b = 0; b <= a; b++) dp[v^1][(10+k-a)%10][(10-b)%10] = min(dp[v^1][(10-a+k)%10][(10-b)%10], dp[v][j][k]+t); } v ^= 1; } cout<<dp[v][0][0]<<endl;//输出把第l-1位转好后，第l位和l+1位分别转了0位的最小值； } return 0; }

注释有什么不对的可以提出来；