題目大意：
給兩個長度相等的數字串s1,s2。每次操作可以把連續的最多三位都+1或-1，如果超過9則變成0，如果小於0則變成9.問從s1到s2最少的步數。
解題思路：
每一位移動正確最多5位，如果一位一位的移動最多需要1000*5=5000 。
長度有1000太大，不能直接用BFS。
因為每次改變最多只影響3位，前面的i-3位不改變，所以可以設dp[i][j][k]表示處理到了第i位，且最後兩位分別為j,k時，前面的i-2位為原串s1時，達到最終的s2的前i位時移動的最小的步數。
轉移時，先把第i位移動正確，然後枚舉在移動第i位時，前面兩位可能到達的狀態，此時第i-2位移動的步數要小於等於第i-1位的，第i-1位的要小於等於第i位的，然後根據dp[i-1]的狀態更新dp[i]的狀態。
比如有三位分別需要移動2 3 4位 第3位需要移動4位，在移動第3位時，可以先都移動2位，然後再後兩位移動1位，最後一位再移動一位。
這類的dp做的比較少，以後多分析各種狀態。
代碼：
<SPAN style="FONT-SIZE: 14px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
#define Maxn 1100
//最多只有1000*5
int dp[Maxn][12][12]; //dp[i][x][y]表示處理到了當前i位，且最後兩位是x和y的，轉到最後的i位所需的最小步數
int a[Maxn],b[Maxn];
char sa[Maxn];
int main()
{
while(~scanf("%s",sa))
{
int n=strlen(sa);
for(int i=1;i<=n;i++)
a[i]=sa[i-1]-'0';
scanf("%s",sa);
for(int i=1;i<=n;i++)
b[i]=sa[i-1]-'0';
memset(dp,INF,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int x=0;x<=9;x++)
{
if(i==1&&x) //只有1位的話全部處理為x=0的情況
continue;
for(int y=0;y<=9;y++)
{
int up=(b[i]-y+10)%10; //當前位一定要達到要求
int dow=(y-b[i]+10)%10;
if(i==1) //此時x一定為0
dp[i][x][y]=min(up,dow);
else if(i==2)
{
int xx=0; //i-2位置為0，表示只有一位的情況
for(int j=0;j<=up;j++) //正轉
{
int yy=(x+j)%10; //在當前位達到要求時，前面一位最多可以移動up位
dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+up);
}
for(int j=0;j<=dow;j++) //反轉
{
int yy=(x-j+10)%10;
dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+dow);
}
}
else //枚舉 操作第i位up或dow時，第i-1位和第i-2位能夠到達的狀態
{
for(int j=0;j<=up;j++) //2 3 4 先三個移動2 再後面兩個移動1 最後一個再移動1
for(int p=j;p<=up;p++) //必須滿足第i-1位移動的大於等於第i-2位，
{
int xx=(a[i-2]+j)%10;
int yy=(x+p)%10;
dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+up);
}
for(int j=0;j<=dow;j++)
for(int p=j;p<=dow;p++)
{
int xx=((a[i-2]-j)+10)%10;
int yy=(x-p+10)%10;
dp[i][x][y]=min(dp[i][x][y],dp[i-1][xx][yy]+dow);
}
}
}
}
}
if(n==1)
printf("%d\n",dp[1][0][a[1]]);
else
printf("%d\n",dp[n][a[n-1]][a[n]]);
}
return 0;
}
</SPAN>
