【DP 训练】Locker, Tianjin 2012, UVa1631

#include<bits/stdc++.h>
using namespace std;
#define maxn 1010
int len;char s1[maxn],s2[maxn];
int dp[maxn][15][15],a[maxn],b[maxn];
//dp（i，x，y）表示翻到i位第i+1位为x，第i+2位为y的最小步数，枚举上翻状态，找到正翻和倒翻的最小值。
int main()
{
	ios::sync_with_stdio(false);
	while(cin>>s1+1>>s2+1)
	{
		len = strlen(s1+1);
		memset(dp,0x3f,sizeof(dp));
		for(int i=1;i<=len;i++)
			a[i] = s1[i]-'0',b[i] = s2[i]-'0';
		a[len+1]=b[len+1]=a[len+2]=b[len+2]=0;
		dp[0][a[1]][a[2]] = 0;
		for(int i=1;i<=len;i++)
		{
			for(int x=0;x<=9;x++)
			{
				for(int y=0;y<=9;y++)
				{//@枚举dp[i-1][x][y] => dp[i][change(x)][change(y)] 
					int d = (b[i]-x+10)%10;//x上翻到目标状态的补数 
					for(int j=0;j<=d;j++)
					{
						for(int k=0;k<=j;k++)
						{
							dp[i][(y+j)%10][(a[i+2]+k)%10]=min(dp[i][(y+j)%10][(a[i+2]+k)%10],dp[i-1][x][y]+d);
						}
					}
					d = 10-d;//下翻
					for(int j=0;j<=d;j++)
					{
						for(int k=0;k<=j;k++)
						{
							 dp[i][(y-j+10)%10][(a[i+2]-k+10)%10]=min(dp[i][(y-j+10)%10][(a[i+2]-k+10)%10],dp[i-1][x][y]+d);
						}
					}					
					
				}
				
			}			
			
		}
		cout<<dp[len][0][0]<<endl;
	}
	return 0;
}