题目链接

   本题是2003年icpc欧洲区域赛中欧赛区的D题

题意

   骰子的六面展开图如下，现在把骰子的六个面赋予一套权重$w_i(1\le w_i\le 50,1\le i\le 6)$，每翻转一次骰子的代价是翻转转后顶面的权重。

   有一个4行无数列的网格桌子，初始时骰子顶面是1点，正面是2点（面向玩家），放置在$(x_1,y_1)$格子处，每次可以将骰子翻转到上下左右之一的相邻格子，翻转的代价是反转后顶面的权重，求将骰子翻转到$(x_2,y_2)$格子处的最小代价$(-1000000000\le x_1,x_2\le 1000000000,1\le y_1,y_2\le 4)$。

分析

   题意倒是好理解，但是题目的sample数据和uDebug上标程的输出不一致，巨坑。

1 2 3 8 1 4
-1 1 0 2

   题目说sample输出是7，然而标程输出是5，反而下面这个数据标程才是输出7。

1 2 8 3 1 4
-1 1 0 2

   这其实就是行从上到下还是从下到上编号的区别，如下图所示。

   可见行从下往上是sample的输出是7，行从上往下输出是5（和标程相同），因此采用行从上往下处理。

   骰子不管在哪个网格，有24种状态，乘上行数4，总共96，起点到终点的横坐标跨度$dx$可能很大，考虑稀疏表/倍增法可将复杂度优化到$O(96^3\log dx)$（不超过$3\times 10^7)$：记$a[y_1][s_1][y_2][s_2][i]$表示骰子在第$y_1$行状态为$s_1$，翻转到第$y_2$行状态为$s_2$且横向移动量为$2^i$（$1\le y_1,y_2\le 4,0\le s_1,s_2<24,0\le i<31$）的最小代价。

   这就需要求出初始横向移动量为1的最小代价$a[y_1][s_1][y_2][s_2][0]$，考虑到向右（或者向左）移动量为1的最小代价可能通过反方向移动更大的量再翻转回来（或者从其它行移动更大的量再翻转回来）而取得，如果横向移动动范围的极限能分析出来，并且极限比较小，则可以利用Dijkstra求得。

   一个感性的结论是：横向移动范围的极限是19（向左/向右9，加上0），因为绕骰子三条轴任意一条翻转的不同权重最多也就4种并且顺/逆时针连续翻转以4为周期，如果绕某轴顺/逆时针净翻转（有可能顺时针翻转了2次逆时针翻又转回来一次，最终顺时针净翻转了一次）了4次以上最终横向移动量达到1，完全可以净翻转少于4次达到同样的结果并且代价更小，三条不同轴总共最多净翻转9次，即便全部贡献给横向移动（纵向移动也可能占用净翻转），向左/向右的最大移动量也才9。

   因此确实可以用Dijkstra求出初始横向移动量为1的最小代价：记$d[y_1][s_1][y_2][s_2][l]$表示骰子在第$y_1$行状态为$s_1$，翻转到第$y_2$行状态为$s_2$且横向移动量为$l$的当前最小代价（$1\le y_1,y_2\le 4,0\le s_1,s_2<24,0\le l<19$，如果横向移动量是负数$x$，则用$19+x$来替代），对每个出发结点$(y_1,s_1)$,将其和初始值$d[y_1][s_1][y_1][s_1][0]=0$入优先级队列跑一遍Dijkstra，最终$d[y_1][s_1][y_2][s_2][1]$就是所求。

测试数据

   给一份CERC 2003官方的整套题解和测试数据。

AC 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

#define L 19
long long d[4][24][4][24][L], a[4][24][4][24][31], e[2][4][24]; bool f[4][24][L];
int c[][2] = {{2, 3}, {6, 3}, {6, 5}, {6, 2}, {6, 4}, {2, 4}}, w[7], x1, y1, x2, y2;

struct node {
    int y, s, x; long long d;
    bool operator< (const node &rhs) const {
        return d > rhs.d;
    }
} t;

int encode(int t, int f) {
    --t;
    return (t<<2) + (f == c[t][0] ? 0 : (f == c[t][1] ? 1 : (f == 7-c[t][0] ? 2 : 3)));
}

void decode(int s, int &t, int &f) {
    t = s>>2; f = s&3; f = f < 2 ? c[t++][f] : 7-c[t++][f-2];
}

void roll(int s, int d, int &t, int &f) {
    int t0, f0; decode(s, t0, f0); int (&e)[2] = c[t0-1];
    if (d == 0) t = f0, f = 7-t0;
    else if (d == 1) t = 7-f0, f = t0;
    else if (d == 2) t = f0 == e[0] ? 7-e[1] : (f0 == e[1] ? e[0] : (f0 == 7-e[0] ? e[1] : 7-e[0])), f = f0;
    else t = f0 == e[0] ? e[1] : (f0 == e[1] ? 7-e[0] : (f0 == 7-e[0] ? 7-e[1] : e[0])), f = f0;
}

long long solve() {
    for (int i=1; i<7; ++i) cin >> w[i];
    cin >> x1 >> y1 >> x2 >> y2; x2 -= x1; --y1; --y2;
    priority_queue<node> q; memset(d, 1, sizeof(d));
    for (int i=0; i<4; ++i) for (int j=0; j<24; ++j) {
        long long (&r)[4][24][L] = d[i][j]; q.push({i, j, 0, r[i][j][0] = 0}); memset(f, 0, sizeof(f));
        while (!q.empty()) {
            t = q.top(); q.pop(); int y = t.y, s = t.s, x = t.x > (L>>1) ? t.x-L : t.x; long long d = t.d;
            if (f[y][t.x][s]) continue;
            f[y][t.x][s] = true;
            for (int k=0; k<4; ++k) {
                int u = k<2 ? (k ? y-1 : y+1) : y, v = k<2 ? x : (k>2 ? x+1 : x-1), t, f, g; roll(s, k, t, f);
                if (u<0 || u>3 || abs(v) > (L>>1)) continue;
                if (v < 0) v += L;
                if (d + w[t] < r[u][g = encode(t, f)][v]) q.push({u, g, v, r[u][g][v] = d + w[t]});
            }
        }
    }
    for (int y=0; y<4; ++y) for (int s=0; s<24; ++s) e[0][y][s] = d[y1][0][y][s][0];
    int b = x2<0 ? L-1 : 1, k = 0, c = 0; x2 = abs(x2); memset(a, 1, sizeof(a));
    for (unsigned int i=x2; (1<<k) <= i; ++k);
    for (int y=0; y<4; ++y) for (int s=0; s<24; ++s) for (int u=0; u<4; ++u) for (int v=0; v<24; ++v)
        a[y][s][u][v][0] = d[y][s][u][v][b];
    for (int w=1; w<k; ++w) for (int y=0; y<4; ++y) for (int s=0; s<24; ++s)
    for (int u=0; u<4; ++u) for (int v=0; v<24; ++v) for (int i=0; i<4; ++i) for (int j=0; j<24; ++j)
        a[y][s][u][v][w] = min(a[y][s][u][v][w], a[y][s][i][j][w-1] + a[i][j][u][v][w-1]);
    if (k--) {
        for (; x2 && k>=0; --k) if ((1<<k) <= x2) {
            for (int y=0; y<4; ++y) for (int s=0; s<24; ++s) {
                long long &r = e[c^1][y][s] = 200000000000;
                for (int u=0; u<4; ++u) for (int v=0; v<24; ++v) r = min(r, e[c][u][v] + a[u][v][y][s][k]);
            }
            c ^= 1; x2 -= 1<<k;
        }
    }
    long long ans = e[c][y2][0];
    for (int i=1; i<24; ++i) ans = min(ans, e[c][y2][i]);
    return ans;
}

int main() {
    int t; cin >> t;
    for (int k=0; k<t; ++k) {
        if (k) cout << endl;
        cout << solve() << endl;
    }
    return 0;
}