本文主要是介绍ACM/ICPC 2012 天津 - HDU 4433 - DP(顺推)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：动态规划（顺推）
注意：在第一个字符之前加一个‘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]);}
}
这篇关于ACM/ICPC 2012 天津 - HDU 4433 - DP(顺推)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
