Locker UVA

一道相对简单的DP问题，之所以简单是因为状态转移比较容易想

最初是想用一维就解决这个问题的，但是代码bug太多放弃了

所以去看题解发现别人用的是四维，而且代码相当简洁，对比我用一维的思路，发现其实思想差不多，只不过增加维度后代码难度减少了很多，用一维的话需要你自己去计算怎么带动其他两位可以达到最优，这个稍微复杂点

代码参考别人

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=(n);i>=0;i--)
using namespace std;
typedef pair <int, int> pii;
typedef long long ll;
typedef unsigned long long llu;
const int inf = 0x3f3f3f3f;
const int dr[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
const int dc[] = { -1, 0, 1, 0, -1, 1, -1, 1 };
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int maxn = 1000 + 5;
char s1[maxn], s2[maxn];
int a[maxn], b[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;else                t = 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];else                t = x + 10 - b[cur];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;}
}