題意：有一個(gè)n（n≤1000）位密碼鎖，每位都是0～9，可以循環(huán)旋轉(zhuǎn)。每次可以讓1～3個(gè)相鄰 數(shù)字同時(shí)往上或者往下轉(zhuǎn)一格。例如，567890->567901（最后3位向上轉(zhuǎn)）。輸入初始狀態(tài) 和終止?fàn)顟B(tài)（長(zhǎng)度不超過(guò)1000），問(wèn)最少要轉(zhuǎn)幾次。例如，111111到222222至少轉(zhuǎn)2次，由 896521到183995則要轉(zhuǎn)12次。

分析：分成兩種情況向上轉(zhuǎn)和向下轉(zhuǎn)，題目說(shuō)可以同時(shí)轉(zhuǎn)1~3，所以不用擔(dān)心轉(zhuǎn)多要回溯之類(lèi)的，直接從頭部枚舉到尾部。確定了方向，就開(kāi)始枚舉后兩位的轉(zhuǎn)動(dòng)次數(shù)，i+1位<=i，i+2<=i+1，這里面是轉(zhuǎn)動(dòng)次數(shù)的比較。

#include<iostream> #include<algorithm> #include<math.h> #include<string.h> #include<stdio.h> #include<string> #include<vector> #include<queue> #include<map> #include<sstream> #include<cassert> #include<set>using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int maxn = 1000+10; int a[maxn], b[maxn]; char s1[maxn], s2[maxn]; int d[maxn][10][10][10]; int len;int dp(int cur, int x, int y, int z) {if (cur >= len )return 0;int &ans = d[cur][x][y][z];if (ans != -1)return ans;ans = INF;int t;if (x <= b[cur])t = b[cur] - x;elset = b[cur] + 10 - x;for (int j = 0; j <= t; j++) {for (int k = 0; k <= j; k++) {ans = min(ans, dp(cur + 1, (y + j) % 10, (z + k) % 10, a[cur + 3]) + t);}}if (x >= b[cur])t = x - b[cur];elset = 10 - (b[cur]-x);for (int j = 0; j <= t; j++) {for (int k = 0; k <= j; k++) {ans = min(ans, dp(cur + 1, (y - j + 10) % 10, (z - k + 10) % 10, a[cur + 3]) + t);}}return ans;} int main() {while (cin>>s1>>s2) {memset(d, -1, sizeof(d));len = strlen(s1);for (int i = 0; i < len; i++) {a[i] = s1[i] - '0';b[i] = s2[i] - '0';}a[len] = a[len + 1] = b[len] = b[len + 1]=0;cout << dp(0, a[0], a[1], a[2]) << endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的uva1631的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。