題目:Circling Round Treasures:CodeForces - 375C

題意:

給你一個N*M的地圖(N,M<=20),地圖上’#'表示障礙物，'B’表示炸彈，數字表示寶藏（炸彈個數+寶藏個數<=8），每個寶藏有價值（-200<=v<=200），'S’表示出發點。每次移動可以從一個格子移動到相鄰格子。尋找一條路徑從’S’出發再回到’S’的路徑，移動步數記為K，這個路徑所包圍的寶藏價值總和記為V，則這條路徑的價值為V-K。題目即是求可行的最大的路徑價值，并且不能包圍炸彈。

思路:

這里一定要注意到寶藏和炸彈個數和小于等于8個。這樣就可以用狀壓+BFS了。用F[X][Y][S]記錄最優狀態，S是$2^8$的狀壓，表示8個寶藏（或炸彈）目前是否被包含在路徑中。F[X][Y][S]表示位于（X,Y）位置時，8個寶藏（或炸彈）包含狀態為S時的路徑最大價值。
一個寶藏（或炸彈）是否被包含，只要向右做一個射線，如果碰到奇數個路徑點那就是包含，否則偶數為不包含。所以經過一個點時，同行左側的寶藏（或炸彈）包含情況會被反轉，重點都說完了，后面自己思考吧。

代碼：

#include<iostream> #include<cstdio> using namespace std; const int nex[4]={1,-1,0,0},ney[4]={0,0,-1,1},q_size=410*(1<<8); int n,m,sx,sy,ans,cnt,va[10],vx[10],vy[10],qx[q_size],qy[q_size],ql[q_size],qs[q_size],b[23][23][1<<8]; char mp[23][23]; inline int get_si(int x,int y){int ans=0;for (int i=1;i<=cnt;++i) if (vx[i]==x&&vy[i]>y) ans|=1<<i-1;return ans; } int main(){scanf("%d%d",&n,&m);for (int i=1;i<=n;++i) scanf("%s",mp[i]+1);for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (mp[i][j]>='0'&&mp[i][j]<='9') ++cnt,vx[mp[i][j]-48]=i,vy[mp[i][j]-48]=j;for (int i=1;i<=cnt;++i) scanf("%d",&va[i]);for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (mp[i][j]=='B') va[++cnt]=-1e8,vx[cnt]=i,vy[cnt]=j;else if (mp[i][j]=='S') mp[i][j]='.',sx=i,sy=j;int h=0,t=1;qx[1]=sx;qy[1]=sy;while (++h<=t){if (qx[h]==sx&&qy[h]==sy){int sum=0;for (int i=1;i<=cnt;++i) if ((1<<i-1)&qs[h]) sum+=va[i];ans=max(ans,sum-ql[h]);}for (int i=0;i<4;++i){int xx=qx[h]+nex[i],yy=qy[h]+ney[i],no_s=xx!=qx[h]?qs[h]^get_si(min(xx,qx[h]),yy):qs[h];if (mp[xx][yy]=='.'&&!b[xx][yy][no_s]) b[xx][yy][no_s]=1,qx[++t]=xx,qy[t]=yy,ql[t]=ql[h]+1,qs[t]=no_s;}}printf("%d",ans); return 0; }

總結

以上是生活随笔為你收集整理的状压搜索 Circling Round Treasures:CodeForces - 375C的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。