HDU_3651
首先可以把1~0映射成0~9，这样更好处理一些。接着我们可以用f[d][x][y]表示已经输入了d个数、左手指在x、右手指在y这种情况所需要的最少秒数，一开始d[0][4][5]=0，接着我们可以把每个状态看成一个点，每个点都和可能转移到的状态连有一条权值为1的边，抽象成这样的模型之后就可以通过dij求最短路来得到答案了。
#include#include #include #include #define MAXD 110#define INF 0x3f3f3f3fint N, a[MAXD], f[MAXD][10][10], cal[MAXD][10][10];char b[MAXD], ch[128];int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};struct St{ int d, x, y, f; St(){} St(int _d, int _x, int _y, int _f) : d(_d), x(_x), y(_y), f(_f){} bool operator < (const St &t) const { return f > t.f; }};void init(){ int i; for(i = 1; b[i]; i ++) a[i] = ch[b[i]]; N = i - 1;}inline int check(int x, int y){ return x >= 0 && x <= 9 && y >= 0 && y <= 9 && x < y;}void solve(){ int i, j, x, y, d; St st; std::priority_queue q; memset(f, 0x3f, sizeof(f)); f[0][4][5] = 0, q.push(St(0, 4, 5, 0)); memset(cal, 0, sizeof(cal)); while(!q.empty()) { st = q.top(), q.pop(); if(st.d == N) break; if(cal[st.d][st.x][st.y]) continue; cal[st.d][st.x][st.y] = 1; for(i = 0; i < 9; i ++) { x = st.x + dx[i], y = st.y + dy[i]; if(check(x, y) && f[st.d][x][y] > st.f + 1) f[st.d][x][y] = st.f + 1, q.push(St(st.d, x, y, st.f + 1)); } if(st.x == a[st.d + 1]) { x = st.x; for(i = -1; i <= 1; i ++) { y = st.y + i; if(check(x, y) && f[st.d + 1][x][y] > st.f + 1) f[st.d + 1][x][y] = st.f + 1, q.push(St(st.d + 1, x, y, st.f + 1)); } } if(st.y == a[st.d + 1]) { y = st.y; for(i = -1; i <= 1; i ++) { x = st.x + i; if(check(x, y) && f[st.d + 1][x][y] > st.f + 1) f[st.d + 1][x][y] = st.f + 1, q.push(St(st.d + 1, x, y, st.f + 1)); } } } printf("%d\n", st.f);}int main(){ ch['0'] = 9; for(int i = 0; i < 9; i ++) ch[i + '1'] = i; while(scanf("%s", b + 1) == 1) { init(); solve(); } return 0;}