• luogu P3786 萃香抱西瓜


    P3786 萃香抱西瓜


    题目背景

    伊吹萃香(Ibuki Suika)正在魔法之森漫步,突然,许多西瓜(Suika)从四周飞来,划出了绚丽的轨迹。虽然阵势有点恐怖,但她还是决定抱走一些西瓜。


    题目描述

    萃香所处的环境被简化为一个长为h,宽为w的网格平面。X坐标范围为[1,w],y坐标范围为[1,h]。

    她初始(第1个时刻)站在坐标为sx,sy的方格。

    西瓜可能在任意一个方格出现,在每个时间单位,它们可能向任何一个方向移动,也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为n个,但只有m个西瓜可以被萃香抱走,因为其他都太大了,可能会砸伤她。

    整个过程会持续T个时刻。萃香希望可以抱走全部的m个西瓜,并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻,与该西瓜处于同一位置。另外,由于萃香不愿耗费过多体力到处乱跑,她每个时刻可以选择静止不动,也可以选择移动到相邻的四个格子之一,只要不越出环境边界。如果选择移动到相邻格子,则算作移动了一次。(第1个时刻萃香刚站定,无法移动)

    在每个时刻,如果萃香选择移动,可以认为萃香与西瓜同时从原来的位置移到了新的位置,没有先后顺序。

    萃香想要知道,不被任何一个大西瓜砸中,并得到所有的m个小西瓜的情况下,最少需要移动多少次。


    输入输出格式

    输入格式:

     第一行五个整数h,w,T,sx,sy,含义见题目描述。

    第二行两个整数n,m,含义见题目描述。

    接下来n段数据,每一段描述了一个西瓜的出现位置,时间,移动方式,是否可以被抱走等内容,具体如下:

    首先一行,两个整数t1,t2,表示西瓜在t1时刻出现, t2时刻消失。若t2=T+1,表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。

    接下来一行一个整数a,只能为0或1,0表示这个西瓜需要避开,1表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有m个。

    接下来t2-t1行,每一行两个整数x,y,顺序描述了从t1时刻到t2-1时刻,该西瓜的坐标。西瓜的移动不一定是连续的,并且是一瞬间完成的,所以无需考虑萃香是否站在了移动路径上。

    输出格式:

     如果萃香在整个T时刻内无法避免被大西瓜砸中或者无法收集到所有m个小西瓜,输出-1,否则输出一个整数,表示萃香需要移动的最少次数。


    输入输出样例

    输入样例#1:
    5 5 10 3 3
    1 1
    1 11
    1
    3 4
    5 2
    3 5
    1 1
    5 4
    3 4
    2 1
    1 1
    1 1
    5 5
    输出样例#1:
    1

    说明

    样例说明:第2~4个时刻萃香站着不动,在第6个时刻,西瓜出现在萃香旁边,萃香移动到(3,4)位置即可抱走这个西瓜。

    数据范围和提示:

    子任务可能出现两种特殊性质A和B

    A: 所有西瓜t1=1,t2=T+1

    所有西瓜全程都静止在原地,不会发生移动。

    B:m=0

    共有10个子任务。

    对于子任务1,具有特殊性质A和B

    对于子任务2~3,仅具有特殊性质A

    对于子任务4~5,仅具有特殊性质B

    对于子任务6~10,不具有任何一个特殊性质。

    对于全部子任务

    1<=所有横坐标范围<=w
    1<=所有纵坐标范围<=h
    1<=h,w<=5
    1<=T<=100
    1<=t1<=T
    2<=t2<=T+1
    t1<t2
    1<=n<=20
    0<=m<=10
    m<=n

    一个位置不会同时出现两个或以上西瓜。

    命题人:orangebird   (w:%%%出题人dalao


    出题人玩的一手好梗

    状压SPFA(想不到吧这俩也能放一起)

    因为要抱走的suika最多只有十个,所以可以想到状压,把所有的suika压成一个二进制数,每一位表示是否抱走了这个suika

    dis[t][x][y][s]表示时间为t,位置为(x,y),已经抱走的suika的集合为s的状态下,需要移动的最少次数

    对所有的suika建立一个三维(t,x,y)的分层图,标记在每个时刻哪里有可以抱的小suika(x),哪里有需要躲的大suika(-1),以及哪里没有suika(0)

    然后就可以愉快地跑状压SPFA来找suika了☆

    ……以及出题人的数据似乎没有考虑到起始点有suika的情况?还是s酱提出来的>_<

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int inf=0x3f3f3f3f;
    int h,w,T,sx,sy,n,m,cnt;
    int fx[]={0,-1,1,0,0},fy[]={0,0,0,-1,1};
    int mp[109][9][9],dis[109][9][9][1024];
    bool in[109][9][9][1024];
    struct suika{int t,x,y,s;};
    queue<suika>q;
    void spfa(){
        q.push((suika){1,sx,sy,max(0,1<<mp[1][sx][sy]-1)});
        memset(dis,0x3f,sizeof(dis));
        dis[1][sx][sy][max(0,1<<mp[1][sx][sy]-1)]=0;
        while(!q.empty()){
            suika cur=q.front();q.pop();
            int t=cur.t,x=cur.x,y=cur.y,s=cur.s;
            in[t][x][y][s]=0;
            if(t==T)continue;
            for(int k=0;k<=4;++k){
                int nx=x+fx[k],ny=y+fy[k],nt=t+1,ns=s;
                if(nx<1||nx>h||ny<1||ny>w||mp[nt][nx][ny]<0)continue;
                if(mp[nt][nx][ny])ns|=1<<mp[nt][nx][ny]-1;
                if(dis[nt][nx][ny][ns]>dis[t][x][y][s]+bool(k)){
                    dis[nt][nx][ny][ns]=dis[t][x][y][s]+bool(k);
                    if(!in[nt][nx][ny][ns]){
                        in[nt][nx][ny][ns]=1;
                        q.push((suika){nt,nx,ny,ns});
                    }
                }
            }
        }
    }
    int main(){
        scanf("%d%d%d%d%d",&h,&w,&T,&sx,&sy);
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            int t1,t2,a;scanf("%d%d%d",&t1,&t2,&a);
            if(!a)a=-1;else a=++cnt;
            for(int j=t1;j<t2;++j){
                int x,y;scanf("%d%d",&x,&y);
                mp[j][x][y]=a;
            }
        }
        if(mp[1][sx][sy]<0){cout<<-1<<endl;return 0;}
        spfa();
        int ans=inf;
        for(int i=1;i<=h;++i)
        for(int j=1;j<=w;++j)
        ans=min(ans,dis[T][i][j][(1<<m)-1]);
        if(ans==inf)ans=-1;
        cout<<ans<<endl;
        return 0;
    }
    suika

    by:wypx


     继续吧我luogu的题解粘过来水题解x

    状态压缩+spfa

    考虑到西瓜的数量很少,可行的西瓜m<=10;对于每一个需要拿走的西瓜我们给他一个重新的编号0~m-1;对这m个西瓜用一个单独没有出现过的二进制的一位表示。于是拿走西瓜并判断以前有无拿过这个西瓜就是当前已经拿的状态now或( | )当前西瓜所在的二进制位,所得的数就是当前拿到西瓜的状态。

    对于没有西瓜的位置当前位置是0(当前数或(|)0还是他本身),走到没有西瓜的位置对当前答案没有贡献。

    转移

    用dis[i][j][t][now]表示当前所在点(i,j)时间为t,当前已拿到西瓜的状态为now,当前的西瓜用x表示(x=1<<y)y是重新分配后当前西瓜的编号

    • 1.当前点的状态是now,当前所在点下一秒有一个西瓜,于是就有dis[i][j][t+1][now|x]=dis[i][j][t][now]

    • 2.当前点的状态是now,要到达的地点(to_x,to_y)上有一个可获得的西瓜(x),那么到达这个点的转移是dis[to_x][to_y][t+1][now|x]=dis[i][j][t][now]+1

    • 3.当前点的状态是now,要到达的地点(to_x,to_y)上有一个不可获得的西瓜,那么这个点不能转移.

    • 4.当前点的状态是now,要到达的地点(to_x,to_y)没有西瓜,dis[to_x][to_y][t+1][now]=dis[i][j][t][now]+1

    • 这样通过上面的4步就可以使在当前状态合法,不用考虑后续

    于是想到可行的状态很少,就可以采用bfs,来实现转移优化,spfa,从(sx,sy)开始把当前状态&时间,当前所到的点压成结构体放进队列.最后拿到所有西瓜的状态就是dis[1~h][1~w][T][(1<<m)-1]

    因为用到了spfa,所以最终得到的一定是最小的答案。

    特殊的,当初始点有一个不可获得的西瓜时或最后得到的答案是INF,输出-1。(不可到达)

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #define ll long long
    const int Suika_big=2333333;
    const int maxx=1<<20;
    using namespace std;
    const int tx[6]={0,0,0,1,-1};
    const int ty[6]={0,1,-1,0,0};
    inline int read(){
        int an=0,f=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
        while('0'<=ch&&ch<='9'){an=(an<<3)+(an<<1)+ch-'0';ch=getchar();}
        return an*f;
    }
    int map[7][7][109],dis[7][7][109][1<<12];
    int n,m,h,w,sx,sy,T,cnt;
    int ans=maxx;
    bool flag;
    bool vis[7][7][109][1<<12];
    void prepare(){
        h=read();w=read();T=read();sx=read();sy=read();
        n=read();m=read();
        for(int i=1;i<=n;i++){
            int xx;
            int t1=read(),t2=read(),Suika_p=read();
            if(Suika_p)cnt++,xx=1<<cnt-1;
            else xx=Suika_big;
            for(int j=t1;j<=min(T,t2-1);j++){
                int x=read(),y=read();
                map[x][y][j]=xx;
            }
        }
        if(map[sx][sy][1]==Suika_big){
            cout<<"-1";flag=1;return;
        }
        for(int i=0;i<=h;i++)
        for(int j=0;j<=w;j++)
        for(int t=1;t<=T;t++)
        for(int l=0;l<=(1<<m);l++)
        dis[i][j][t][l]=maxx;
    }
    struct saber{
    int x,y,Suika,t;
    }now;
    queue<saber>q;
    void spfa(){
        q.push((saber){sx,sy,map[sx][sy][1],1});
        dis[sx][sy][1][map[sx][sy][1]]=0;
        while(!q.empty()){
            now=q.front();q.pop();
            vis[now.x][now.y][now.t][now.Suika]=0;
            if(now.t>T)continue;
            for(int i=0;i<=4;i++){
                int xx=now.x+tx[i];
                int yy=now.y+ty[i];
                int melon=now.Suika;
                if(xx<1||yy<1)continue;
                if(xx>h||yy>w)continue;
                int t=now.t+1;
                if(map[xx][yy][t]==Suika_big)continue;
                int diss=dis[now.x][now.y][now.t][now.Suika]+(i!=0);
                melon|=map[xx][yy][t];
                if(dis[xx][yy][t][melon]>diss){
                    dis[xx][yy][t][melon]=diss;
                    if(!vis[xx][yy][t][melon]){
                        q.push((saber){xx,yy,melon,t});
                        vis[xx][yy][t][melon]=1;
                    }
                }
            }
        }
    }
    int main(){
        prepare();
        if(flag){return 0;}
        spfa();
        for(int i=1;i<=h;i++)
            for(int j=1;j<=w;j++)
            ans=min(ans,dis[i][j][T][(1<<m)-1]);
        if(ans==maxx)cout<<"-1";
        else cout<<ans;
        return 0;
    }
    Suika

    by:s_a_b_e_r


  • 相关阅读:
    圆形刻度盘 进度 展示
    弧度、角度换算公式
    placeholder 颜色更改
    移除HTML5 input在type="number"时的上下小箭头
    linux 安装python-setuptools
    通过helm 安装 harbor 不成功问题处理
    k8s 添加ingress 暴露服务
    k8s编辑pod配置信息
    postgres 数据导入导出
    万能视频后台转码
  • 原文地址:https://www.cnblogs.com/ck666/p/7683856.html
一二三 - 开发者的网上家园