【Luogu】P3786萃香抱西瓜（状压DP）

　　题目链接

　　水题，数据范围提示得太明显了吧，不用动脑子都能知道是状压。

　　不过还是有坑（当然更可能是我脑子有坑）

　　f[i][j][k][l]表示当前是第i秒，萃香在（j，k），已经抱到的西瓜状态是l的最少移动次数，然后用BFS一样的办法暴力转移就行，复杂度完全过得去。

　　

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cctype>

#define maxp 7

#define maxt 105

#define maxn 12

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

int f[maxt][maxp][maxp][<<maxn];

int q[maxt][maxp][maxp];

int tot;

int ux[]={,,,-,};

int wy[]={,,,,-};

int main(){

    int h=read(),w=read(),t=read(),sx=read(),sy=read(),n=read(),m=read();

    int lim=<<m;

    memset(f,/,sizeof(f));    int inf=f[][][][];

    f[][sx][sy][]=;

    for(int i=;i<=n;++i){

        int t1=read(),t2=read(),opt=read();

        int to=t2;

        if(t2>t)    t2=t;

        if(opt==){

            tot++;

            for(int j=t1;j<to;++j){

                int x=read(),y=read();

                q[j][x][y]=tot;

            }

        }

        else{

            for(int j=t1;j<to;++j){

                int x=read(),y=read();

                q[j][x][y]=-;

            }

        }

    }

    for(int tme=;tme<=t;++tme){

        for(int i=;i<=h;++i)

            for(int j=;j<=w;++j)

                for(register int k=;k<lim;++k){

                    if(f[tme][i][j][k]==inf)    continue;

                    for(int l=;l<=;++l){

                        int x=i+ux[l],y=j+wy[l];

                        if(x==||y==||x>h||y>w||q[tme+][x][y]==-)    continue;

                        int ret=q[tme+][x][y],now=;

                        if(ret)    now=<<(ret-);

                        f[tme+][x][y][k|now]=min(f[tme+][x][y][k|now],f[tme][i][j][k]+);

                    }

                    if(q[tme+][i][j]!=-){

                        int ret=q[tme+][i][j],now=;

                        if(ret)    now=<<(ret-);

                        f[tme+][i][j][k|now]=min(f[tme+][i][j][k|now],f[tme][i][j][k]);

                    }

                }

    }

    int ans=inf;

    for(int i=;i<=h;++i)

        for(int j=;j<=w;++j)

            if(ans>f[t][i][j][lim-])    ans=f[t][i][j][lim-];

    if(ans==inf)    ans=-;

    printf("%d",ans);

}