Portal --> CF375C

Solution

　　一個有趣的事情：題目中有很大的篇幅在介紹如何判斷一個位置在不在所圍的多邊形中

　　那么。。給了方法當然就是要用啊

?　　首先是不能包含\('B'\)，處理方式很簡單直接把他當成一個值為\(-inf\)的寶藏即可，這樣所有的object就全部可以看成一類了，不需要再額外考慮

　　注意到object的總數很少，考慮狀壓，記\(vis[x][y][st]\)表示當前在\((x,y)\)這個點，射線與路徑的交點數量為奇數的object的狀態為\(st\)，這種局面是否可行，然后對應的開一個\(step[x][y][st]\)表示達到這種局面所需要的最少步數，這個時候。。最短路既視感？

?　　反正\(n\)和\(m\)也不大，所以我們可以考慮跑一個最短路，最后枚舉一下\(st\)，然后用\((x,y)\)為起點位置的狀態去更新一下答案就好了

　　現在的問題是，如何計算一步移動對object的射線的影響

?　　注意到這個射線其實隨便選就好了。。所以方便起見，我們可以欽定每個點只看往其左上方延伸的、角度很小很小很小的一條射線就好了（也可以是別的方向啦隨意隨意，不過角度很小這個比較重要），角度小這個有一個好處就是，因為角度很小所以只有當縱坐標改變的時候才有可能產生交點，然后其他的情況判斷就十分簡單了

　　
　　mark：特殊值什么的是個好東西
　　mark：沒有思路的時候。。可以嘗試從描述里面找提示。。？
　　

?　　代碼大概長這個樣子

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int N=25,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},ST=1<<8; const int inf=1e4; struct Rec{int x,y,val; }a[20]; struct Data{int x,y,st;Data(){}Data(int x1,int y1,int st1){x=x1; y=y1; st=st1;} }; queue<Data> q; int vis[N][N][ST],step[N][N][ST],inq[N][N][ST]; char mp[N][N]; int n,m,t,stx,sty,cnt,ans; int St(int x){return 1<<x-1;} bool in(int st,int x){return st>>(x-1)&1;} bool ok(int x,int y){if (x<1||y<1||x>n||y>m) return false;return mp[x][y]=='.'||mp[x][y]=='S'; } bool check(int x,int y,int nwx,int nwy,int id){if (x==nwx) return false;if (x==a[id].x&&y<a[id].y) return nwx<x;if (nwx==a[id].x&&nwy<a[id].y) return x<nwx;return false; } void bfs(){Data v,u;int x,y,st,xx,yy,nw;while (!q.empty()) q.pop();for (int i=1;i<=n;++i)for (int j=1;j<=m;++j)for (int k=0;k<(1<<cnt);++k)step[i][j][k]=inf,inq[i][j][k]=false;q.push(Data(stx,sty,0)); inq[stx][sty][0]=true;step[stx][sty][0]=0;while (!q.empty()){x=q.front().x; y=q.front().y; st=q.front().st; q.pop();vis[x][y][st]=true;for (int i=0;i<4;++i){xx=x+dx[i]; yy=y+dy[i];if (!ok(xx,yy)) continue;nw=st;for (int j=1;j<=cnt;++j)if (check(x,y,xx,yy,j))nw^=St(j);if (step[xx][yy][nw]>step[x][y][st]+1){step[xx][yy][nw]=step[x][y][st]+1;if (!inq[xx][yy][nw])q.push(Data(xx,yy,nw)),inq[xx][yy][nw]=true;}}inq[x][y][st]=false;} } void get_ans(){int tmp;for (int st=0;st<(1<<cnt);++st){if (!vis[stx][sty][st]) continue;tmp=0;for (int i=1;i<=cnt;++i)if (in(st,i))tmp+=a[i].val;ans=max(ans,tmp-step[stx][sty][st]);} }int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin); #endifscanf("%d%d\n",&n,&m);t=0; cnt=0;for (int i=1;i<=n;++i){for (int j=1;j<=m;++j){scanf("%c",&mp[i][j]);if ('0'<=mp[i][j]&&mp[i][j]<='9'){a[mp[i][j]-'0'].x=i,a[mp[i][j]-'0'].y=j;t=max(t,mp[i][j]-'0');++cnt;}else if (mp[i][j]=='S')stx=i,sty=j;}scanf("\n");}for (int i=1;i<=t;++i) scanf("%d",&a[i].val);for (int i=1;i<=n;++i)for (int j=1;j<=m;++j)if (mp[i][j]=='B')a[++cnt].x=i,a[cnt].y=j,a[cnt].val=-inf;bfs();get_ans();printf("%d\n",ans); }

轉載于:https://www.cnblogs.com/yoyoball/p/9742596.html

總結

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

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