学步园

题意：动态规划（顺推）

注意：在第一个字符之前加一个‘0’，在末尾加两个'0'

dp[i][x][y]表示前i个字符已经调整好，并且第[i+1]为x，[i+2]为y，此状态最少需要的调整次数。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[1010], s2[1010];
int a[1010], b[1010];
int dp[1010][10][10];
const int INF = 999999999;

int main()
{
    while(scanf("%s %s", s1, s2) != EOF)
    {
        int i, j, k, x, y;
        int n = strlen(s1);
        for(i = 0; i < n; i++)
        {
            a[i+1] = s1[i] - '0';
            b[i+1] = s2[i] - '0';
        }
        a[n+1] = a[n+2] = 0;
        b[n+1] = b[n+2] = 0;

        for(i = 0; i <= n; i++)
            for(x = 0; x < 10; x++)
               for(y = 0; y < 10; y++)
                   dp[i][x][y] = INF;

        dp[0][a[1]][a[2]] = 0;
        for(i = 1; i <= n; i++)
        {
            for(x = 0; x < 10; x++)
            {
                for(y = 0; y < 10; y++)
                {
                    int down = (b[i] - x + 10) % 10;
                    for(j = 0; j <= down; j++)
                        for(k = 0; k <= j; k++)
                            dp[i][(y+j)%10][(a[i+2]+k)%10] = min(dp[i-1][x][y] + down,
                                                                dp[i][(y+j)%10][(a[i+2]+k)%10]);
                    int up = 10 - down;
                    for(j = 0; j <= up; j++)
                        for(k = 0; k <= j; k++)
                            dp[i][(y-j+10)%10][(a[i+2]-k+10)%10] = min(dp[i-1][x][y] + up,
                                                                dp[i][(y-j+10)%10][(a[i+2]-k+10)%10]);

                }
            }
        }
        printf("%d\n",dp[n][0][0]);
    }
}