2015
07-16

# 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

by—cxlove

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

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


1. 线路***的固定的，私营化就是变相提价收回成本而已。民间有可能筹出钱修高铁么。还有上面说国内高铁贵的，高铁修在中国就能比修在国外成本低了么。