题解 P2238 【逛庙会】

kkksc03 · 2016-10-15 21:37:15 · 题解

假设我们先考虑同一个小摊，可重复购买的话，会比较简单。也就是说，根据各个摊位，计算要买东西的价格为状态，从(1,1)到(H,W)移动的过程做二维dp。但是不能重复购买，在哪些小摊里买了东西这个也要作为一个状态。因此成了三维状态dp。第三维是状态压缩。

实际上对于一个点，可以向右或者向下扩展。这样可以很大的简化讨论（之前的题解写错了，抱歉）

其中第三维k是0-15一共16种状态，代表上下左右买或者不买，一共2^4=16种状态（如果你非要搞成6维dp我也不说什么）。k'代表合法的状态转移。比如现在的位置有摊位，从左边转移过来的状态中，就不可以购买左边的右边（也就是目前所处的位置）。初始条件就是F[0][0][k]=0。

下面是std

 #include <stdio.h>

#define chmin(a,b) if ((a) > (b)) { a = (b); }

const int INF = 1000000;
int H, W;
int shop[1020][1020];
int dp[1020][1020][16];
int bc[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };//二进制中1的个数

int main()
{
    int i, j, k, k2, cost;
    char in[1020];
    scanf("%d%d", &H, &W);

    for (i = 0; i < H + 3; ++i) {
        for (j = 0; j < W + 3; ++j) {
            shop[i][j] = 0;
            for (k = 0; k < 16; ++k) dp[i][j][k] = INF;
        }
    }

    for (i = 0; i < H; ++i) {
        scanf("%s", in);
        for (j = 0; j < W; ++j) {
            shop[i + 1][j + 1] = (in[j] == '.' ? 0 : (in[j] - '0'));
        }
    }

    dp[1][1][15] = 0;
    for (i = 1; i <= H; ++i) {
        for (j = 1; j <= W; ++j) {
            for (k = 0; k < 16; ++k) {
                // move to (i + 1, j)
                for (k2 = 0; k2 < 16; ++k2) {
                    if (
                        ((k & 4) == 0) != ((k2 & 8) == 0) 
                        ||!(k & 2)
                        ||(bc[k & 1] + bc[k2 & 6] <= 1)
                    ) continue;

                    cost = dp[i][j][k];
                    if (k2 & 1) cost += shop[i + 2][j - 1];
                    if (k2 & 2) cost += shop[i + 2][j];
                    if (k2 & 4) cost += shop[i + 1][j + 1];

                    chmin(dp[i + 1][j][k2], cost);
                }

                // move to (i, j + 1)
                for (k2 = 0; k2 < 16; ++k2) {
                    if (
                        ((k & 2) == 0) != ((k2 & 1) == 0)
                        ||!(k & 4)
                        ||(bc[k & 8] + bc[k2 & 6] <= 1)
                    ) continue;

                    cost = dp[i][j][k];
                    if (k2 & 8) cost += shop[i - 1][j + 2];
                    if (k2 & 4) cost += shop[i][j + 2];
                    if (k2 & 2) cost += shop[i + 1][j + 1];

                    chmin(dp[i][j + 1][k2], cost);
                }
            }
        }
    }

    printf("%d\n", dp[H][W][15]);
    return 0;
}