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; } suikaby: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; } Suikaby:s_a_b_e_r
?
轉載于:https://www.cnblogs.com/ck666/p/7683856.html
總結
以上是生活随笔為你收集整理的luogu P3786 萃香抱西瓜的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 神炎皇 数学
- 下一篇： STM32 keil中编译遇到的问题