题解：P3786 萃香抱西瓜

· · 题解

一个简单的三维 dp 写法

似乎是最优解，先把题解写一下
这题比较麻烦的点在于西瓜只有一条命，搬走后不能蹲刷新点。
由于同一格至多同时有一个西瓜，小西瓜数量很小，于是可以这样：
记 dp(k,t,p) 为第 k 轮时搬走了若干小西瓜并停留在坐标 p 的最少步数。其中 p=5(x-1)+y-1, t 为不超过 2^m 的二进制数，第 i 为 0 代表暂未搬走第 i 个小西瓜，反之亦然。为方便更新，记 f(k,p) 为第 k 轮位置 p 的类型，0 为无瓜，-1 为大西瓜，其余不超过 m 的自然数为小西瓜的编号。这样就可以愉快地 dp 啦，时间复杂度 O(T\times2^m) ，具体过程见代码。 

#include<bits/stdc++.h>
using namespace std;

const int STEPS[4][2] = {-1,0,0,-1,0,1,1,0};

int h, w, t, sx, sy, n, m;
int f[105][25], dp[105][1024][25];

int pos(int r,int c){
    return 5 * ( r - 1 ) + c - 1;
}

void update(int k, int t, int p){
    int r = p / 5 + 1;
    int c = p % 5 + 1;
    //有大西瓜或越界
    if(f[k][p] == -1 || r<1 || r>w || c<1 || c>h){
        dp[k][t][p] = 114514;
        return;
    }
    //若本格有小西瓜，则可以由没搬过这个西瓜的状态前来
    int lt = f[k][p]? t & ~(1<<(f[k][p]-1)) : t;
    dp[k][t][p] = dp[k-1][lt][p];//按兵不动
    for(int i = 0; i < 4; i++){
        int lr = r + STEPS[i][0];
        int lc = c + STEPS[i][1];
        if(lr<1 || lr>w || lc<1 || lc>h){
            continue;
        }
        if(dp[k][t][p] > dp[k-1][lt][pos(lr,lc)]){
            dp[k][t][p] = dp[k-1][lt][pos(lr,lc)]+1;
        }
    }
}

int main(){

    scanf("%d%d%d%d%d%d%d",&h,&w,&t,&sx,&sy,&n,&m);
    for(int i = 0, cnt = 0, t1, t2, a; i < n; i++){
        scanf("%d%d%d", &t1, &t2, &a);
        if(a) cnt++;
        for(int j = t1, x, y; j < t2; j++){
            scanf("%d%d", &x, &y);
            //给小西瓜安排座位
            f[j][pos(x, y)] = a? cnt : -1;
        }
    }

    //第一时刻除出生点外全图不可达
    int maxt = (1<<m)-1;
    for(int t = 0; t <= maxt; t++){
        for(int p = 0; p < 25; p++){
            dp[1][t][p] = 114514;
        }
    }
    //初始时不用动
    int orz = f[0][pos(sx, sy)];
    if(orz){//若初始自带一颗小西瓜
        dp[1][1<<(orz-1)][pos(sx, sy)] = 0;
    }else{
        dp[1][0][pos(sx, sy)] = 0;
    }

    for(int k = 2; k <= t; k++){
        for(int t = 0; t <= maxt; t++){
            for(int p = 0; p < 25; p++){
                update(k, t, p);
            }
        }
    }

    //即使早就抱走全部小西瓜，也只能在第T时刻离开
    int ans = 114514;
    for(int j = 0; j < 25; j++){
        ans = min(ans, dp[t][maxt][j]);
    }

    printf("%d", ans == 114514? -1 : ans);

    return 0;
}

原谅我再次定义了 t，反正局部变量和全局变量重名没影响，就这样吧。
AC 记录 114ms