本文主要是介绍hdu 4433(uva1631) - Locker - dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个密码锁的当前状态，问最少转动多少次可以得到终止状态，每次转可以向上向下，而且转动一个位置的时候可以带动后面的一个或两个位置一块转。
对于每一个位置，记录当该位置已经转完以后带动后面两个位置转动不同次数所需要的最少转动次数。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 1010, INF = 0x3f3f3f3f;
int dp[MAXN][11][11];
char s[MAXN], t[MAXN];
int debug(int n) {for(int i = 0; i <= n; i++) {for(int j = 0; j < 10; j++) {for(int k = 0; k < 10; k++) {printf("%2d ", dp[i][j][k] >= INF ? -1 :dp[i][j][k]);}printf("\n");}printf("\n\n");}
}
int main() {int i, j, k, l;while(~scanf("%s%s", s, t)) {memset(dp, 0x3f, sizeof(dp));dp[0][0][0] = 0;int n = strlen(s);for(i = 0; i < n; i++) {for(j = 0; j < 10; j++) {for(k = 0; k < 10; k++) {int tt = (t[i] - s[i] - j + 20) % 10;for(l = 0; l <= tt; l++) {for(int m = 0; m <= l; m++) {int nk = (k + l) % 10;dp[i + 1][nk][m] = min(dp[i + 1][nk][m], dp[i][j][k] + tt);}}tt = (s[i] + j - t[i] + 10) % 10;for(l = 0; l <= tt; l++) {for(int m = 0; m <= l; m++) {int nk = (k - l + 10) % 10;dp[i + 1][nk][(10 - m) % 10] = min(dp[i + 1][nk][(10 - m) % 10], dp[i][j][k] + tt);}}}}}
// debug(n);printf("%d\n", dp[n][0][0]);}return 0;
}这篇关于hdu 4433(uva1631) - Locker - dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
