題面

傳送門

題解

首先要解決一個問題，就是怎么判斷一個點是否在多邊形內(nèi)部

從這個點向某一個方向做一條射線，如果這條射線和多邊形的交點為奇數(shù)說明在多邊形內(nèi)，否則在多邊形外

然而有一些特殊情況，比方說一個多邊形\((0,0),(2,0),(2,1),(1,1),(1,2)\)，如果一個點\((1,1)\)向上做射線和這個多邊形有兩個交點，然而這個點還是在多邊形內(nèi)部的

那么我們可以通過加一些\(eps\)之類的來避免這種情況，具體可以看代碼

把所有的豆子狀壓，枚舉起點\((x,y)\)，設(shè)\(f_{i,j,s}\)表示到了\((i,j)\)，圍住的豆子的情況為\(s\)的情況下的最小步數(shù)，那么最后\(f_{x,y,s}\)就是走了一個回路之后圍住豆子情況為\(s\)的最小步數(shù)

//minamoto #include<bits/stdc++.h> #define R register #define inf 0x3f3f3f3f #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; const int N=15,M=(1<<9)+5; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int f[N][N][M],vis[N][N][M],sum[M],val[N],xi[N],yi[N]; struct node{int x,y,s;node(R int xx,R int yy,R int ss):x(xx),y(yy),s(ss){}}; queue<node>q;char mp[N][N]; int n,m,d,res=-2e9,lim; inline int get(R int x,R int y,R int xx,R int yy,R int s){fp(i,0,d-1)if((x==xi[i]&&xx>xi[i]||x>xi[i]&&xx<=xi[i])&&yy>yi[i])s^=(1<<i);return s; } void solve(int x,int y){q.push(node(x,y,0));fp(i,1,n)fp(j,1,m)fp(s,0,lim-1)f[i][j][s]=inf; // memset(f,0x3f,sizeof(f));f[x][y][0]=0,vis[x][y][0]=1;while(!q.empty()){int x=q.front().x,y=q.front().y,s=q.front().s;q.pop();vis[x][y][s]=0; // printf("%d %d %d\n",x,y,s); // if((x<1||x>n)&&(y<1||y>m)&&(s<0||s>=lim))puts("qwq");fp(k,0,3){int nx=x+dx[k],ny=y+dy[k];if(mp[nx][ny]!='0')continue;int ns=k<2?get(x,y,nx,ny,s):s;if(cmin(f[nx][ny][ns],f[x][y][s]+1)&&!vis[nx][ny][ns])q.push(node(nx,ny,ns)),vis[nx][ny][ns]=1;}}fp(i,0,lim-1)cmax(res,sum[i]-f[x][y][i]); } int main(){ // freopen("testdata.in","r",stdin);scanf("%d%d%d",&n,&m,&d),lim=(1<<d);fp(i,0,d-1)scanf("%d",&val[i]);fp(i,0,lim-1)fp(j,0,d-1)if(i>>j&1)sum[i]+=val[j];fp(i,1,n)scanf("%s",mp[i]+1);fp(i,0,n+1)mp[i][0]=mp[i][m+1]='#';fp(j,0,m+1)mp[0][j]=mp[n+1][j]='#';fp(i,1,n)fp(j,1,m)if(mp[i][j]>='1'&&mp[i][j]<='9')xi[mp[i][j]-'1']=i,yi[mp[i][j]-'1']=j;fp(i,1,n)fp(j,1,m)if(mp[i][j]=='0')solve(i,j);printf("%d\n",res);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bztMinamoto/p/10513068.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P2566 [SCOI2009]围豆豆（状压dp+计算几何）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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