題目：給出兩個串，每次可以選擇連續的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;
}
