題目大意

給定一個$n\times m$的網(wǎng)格$(n,m\leq 20)$，每個格子都是$S\space \#\space B\space x\space .$中第一個。

$S$表示起點，保證有且僅有一個。

$\#$表示障礙，不能通過,$.$表示空地，可以通過

$B$表示炸彈，$x$是一個數(shù)字，每個數(shù)子代表著一個寶藏，每個寶藏有對應的價值（可以為負）。

炸彈和寶藏的數(shù)量不超過$8$個

現(xiàn)在你要規(guī)劃一條從$S$出發(fā)，每次只能沿著上下左右四個方向，只能經(jīng)過除了空地和起點的可以自交的閉合回路，使得這條回路縮圈起來的格子中不含有炸彈，將圈起來的格子中所有寶藏之和加起來記為$sum$，路徑長度記為$len$，求$\max(sum-len)$。

舉個例子

這遍是原圖中的最優(yōu)解。

?

題解

我們先想辦法解決如何判斷一個點是否在回路內。

考慮一個點$(i,j)$（第$i$行第$j$列），從它出發(fā)向左下作一條方向無限貼近于正下的射線，通過這條射線與回路相交次數(shù)的奇偶性來判斷，即枚舉所有$k(k>i)$，計算$sum$表示回路經(jīng)過$(k,j),(k,j-1)$兩個點之間的次數(shù)和。

若$sum$為奇數(shù)，那么在形內，否則在形外。

?

接下來就簡單了，由于炸彈和寶藏的和不超過$8$個，我們直接將炸彈看做價值為$-INF$的寶藏，然后每個寶藏是否在形內進行裝狀態(tài)壓縮。

這樣就可以從起點出發(fā)進行$BFS$了，$F_{(i,j,k)}$表示從$S$出發(fā)，到達$(i,j)$，所有寶藏是否在形內的情況為$k$的最短步數(shù)。最后只需枚舉狀態(tài)進行計算取$\max$即可。

最終復雜度為$O(nmk2^k)$，我圖著省事把其中一個$k$改成了$n$也能過。

?

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define M 30 #define bas 1000 #define INF 10000000 using namespace std; int read(){int nm=0,fh=1; char cw=getchar();for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');return nm*fh; } const int dx[]={0,0,-1,1},dy[]={-1,1,0,0}; int n,m,q[INF],dis[M][M][550],pos[M][M],T,B,tot,val[M]; int xt[M],yt[M],xb[M],yb[M],hd,tl,Sx,Sy,ans; char ch[M]; void ins(int x,int y,int sta){q[tl++]=(x*bas+y)*bas+sta;} void tk(int &x,int &y,int &sta){sta=q[hd]%bas,q[hd]/=bas,y=q[hd]%bas,q[hd]/=bas,x=q[hd],hd++;} int main(){n=read(),m=read(),memset(dis,0x3f,sizeof(dis));for(int i=1;i<=n;i++){scanf("%s",ch+1);for(int j=1;j<=m;j++){if(ch[j]=='.') continue;if(ch[j]=='B') B++,xb[B]=i,yb[B]=j,pos[i][j]=++tot,val[tot]=-INF;else if(ch[j]=='#') pos[i][j]=-1;else if(ch[j]=='S') ins(i,j,0),Sx=i,Sy=j,dis[i][j][0]=0;else ++T,xt[ch[j]-'0']=i,yt[ch[j]-'0']=j,pos[i][j]=++tot;}}for(int i=1;i<=T;i++) val[pos[xt[i]][yt[i]]]=read();while(hd<tl){int x,y,now; tk(x,y,now);for(int j=0;j<4;j++){int xx=x+dx[j],yy=y+dy[j],rem=now;if(pos[xx][yy]||xx<1||yy<1||xx>n||yy>m) continue;if(y!=yy){for(int j=1,nw=max(y,yy);j<xx;j++)if(pos[j][nw]>0) rem^=(1<<(pos[j][nw]-1));}if(dis[xx][yy][rem]<INF) continue;dis[xx][yy][rem]=dis[x][y][now]+1,ins(xx,yy,rem);}}for(int i=1;i<(1<<tot);i++){int res=0;for(int dt=1;dt<=tot;dt++) if((i>>(dt-1))&1) res+=val[dt];ans=max(ans,res-dis[Sx][Sy][i]);} printf("%d\n",ans); return 0; }

?

　　

?

?

?

?

轉載于:https://www.cnblogs.com/OYJason/p/9743321.html

總結

以上是生活随笔為你收集整理的CF221C Circling Round Treasures的全部內容，希望文章能夠幫你解決所遇到的問題。

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