1 条题解
-
0
自动搬运
来自洛谷，原作者为
hzoi_liuchang
AFO搬运于
2025-08-24 21:39:08，当前版本为作者最后更新于2020-04-15 11:40:46，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
分析
一看到是方格中的问题，数据范围又在10以下，显然是状态压缩DP了
这道题的细节比较多，而且用到了位运算，所以有些代码不太好理解，因此我感觉分块讲会比较好理解
问题一、数组的定义
如果你要进行动态规划，肯定要开一个数组存储存储结果
这道题开二维数组显然是不够用的，因为我们既要记录一个点的横坐标，又要记录一个点的纵坐标
我们设f[x][y][s]为走到坐标为（x,y）的点，且状态为S时所走过的路程长度
x,y的含义大家应该很容易就可以理解，关键是状态S
我们可以这样想在方格中最多有9个豆豆，所以我们可以用一个长度为9的二进制数来存储状态
什么意思呢？我们还是来举一个例子
比如说方格中有4个豆子，那么
0 0 0 0 表示你一个豆子也没有围上
0 0 1 0 表示你把第二个豆子围上
0 1 1 1 表示你把第1、2、3个豆子全部围上
这样的话大家应该就可以理解了
这里还需要注意的是，因为我们每一次开始遍历的起点不同，所以最终得到的答案也不同，因此我们每选择一个起点，就要重新将f数组初始化
问题二、围住的判断
只有某一颗豆在路径所形成的多边形（可能是含自交的复杂多边形）的内部时，我们才可以得到这个豆子的价值
我们来举几个例子
我们可以看到，左边的这两幅图中豆豆是可以被围住的，而右边的这两幅图中，豆豆是无法被围住的那么它们分别有什么特点呢？
我们从豆豆开始向右引一条射线（其实向哪一个方向都可以），如果射线与路径的交点为奇数个，那么豆豆能被围住，反之则不能
（这其实就是射线定理，大家有兴趣的话可以百度一下证明）
这样的话，我们只要判断路径与射线的交点个数是不是就可以了呢
其实还是不行，比如下面这幅图
射线与路径的交点有三个（绿色的圈圈住的部分），但是豆豆没有被包含在里面所以只有当上下移动时，我们才可以给路径计数，如果是左右水平移动的话，我们就不能算进去
这是对于上下移动的判断，mx、my分别是移动之前点的横纵坐标，nx、ny分别是移动之后点的横纵坐标ax数组记录的是所有豆豆的横坐标，ay数组记录的是所有豆豆的纵坐标
前面的四个判断是对于上下移动的判断，只有上下移动才可以计数
最后一个判断是判断该路径是否在豆豆的右边（因为我是向右引的射线）
当然你把里面的==都改成>=也可以，但是没有必要，因为你一次只能走一个格子
问题三、怎么由上一个格子的状态ms推出下一个格子的状态ns
先上代码
int solve(int mx,int my,int nx,int ny,int ms){ int ns=ms; for(int i=1;i<=d;i++){ if(((mx==ax[i] && nx<ax[i]) || (mx<ax[i] && nx==ax[i])) && ny>ay[i]){ ns^=(1<<(i-1)); } } return ns; }mx、my分别是移动之前点的横纵坐标，nx、ny分别是移动之后点的横纵坐标
ms是上一个格子的状态，ns是下一个格子的状态（什么是状态我们在第一个问题中已经提到过了）
ax数组记录的是所有豆豆的横坐标，ay数组记录的是所有豆豆的纵坐标
在第三行我们枚举每一个豆豆，在第四行我们判断当前移动能否计数（问题二中已经说过）
最关键的就是第五行 ns^=(1<<(i-1))
这是什么意思呢，我们可以这样考虑
ns必定要由ms推导出来，我们枚举每一个豆豆，如果当前走的路径可以与射线相交，那么必定会改变交点个数的奇偶性
也就是说，豆豆本来在四边形内，走了这一步，就到了四边形外；或者豆豆本来在四边形外，走了这一步，就到了四边形内
我们知道状态S如果从右往左数第i位为1，则说明第i个豆豆在格子内，反之亦然
那么如果从右往左数第i位状态变化了，我们只需要将当前的状态和（1<<(i-1)）取异或，就相当于把第i为取反，其他位不变
这样就达到了我们的目的
（我感觉已经讲得很清楚了，如果再不理解，我也没有办法了）
问题四、通过什么来算出f数组呢
我们可以用SPFA，也可以用bfs
不同的是bfs每个元素只会进栈一次，而SPFA可以进很多次
但是实际上你即使用SPFA每个点也只会松弛一次，因为你的路径只会越走越长用bfs和用SPFA没什么区别
但是要注意vis数组的初始化，用bfs的话vis数组必须初始化，但是用SPFA则不用
因为SPFAvis数组最后的状态必定都0
最终的状态转移方程为：ans=max(ans,val[i]-f[ii][jj][i]) val[i]是我们预处理出来的状态为i时豆子的总价值，预处理过程如下:
for(int i=0;i<mmax;i++){ for(int j=1;j<=d;j++){ if(i&(1<<(j-1))) val[i]+=da[j]; } }da[j]是第j个豆子的价值，ans使我们最终要的结果
豆子的总价值减去路程上的花费得出来的结果，最后再取一个最大值显然是我们想要的ans
代码（前面该说的都说了，注释我就少加点）
bfs版
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; int n,m,d; int mmax,f[11][11][1<<11],da[11],val[1<<11]; struct asd{ int x,y,s; asd(int aa=0,int bb=0,int cc=0){ x=aa,y=bb,s=cc; } };//跑bfs的结构体 char c[11][11]; int xx[4]={0,-1,0,1},yy[4]={-1,0,1,0},ax[11],ay[11]; //xx,yy枚举走的方向，ax,ay记录豆豆的横纵坐标 int ans=-0x3f3f3f3f;//记录最终价值 int vis[11][11][1<<11];//判断该点是否已经遍历过 int solve(int mx,int my,int nx,int ny,int ms){ int ns=ms; for(int i=1;i<=d;i++){ if(((mx==ax[i] && nx<ax[i]) || (mx<ax[i] && nx==ax[i])) && ny>ay[i]){ ns^=(1<<(i-1)); } } return ns; } void bfs(int ii,int jj){ queue<asd> q; q.push(asd(ii,jj,0)); memset(f,0x3f,sizeof(f)); memset(vis,0,sizeof(vis)); f[ii][jj][0]=0; while(!q.empty()){ asd aa=q.front(); q.pop(); int mx=aa.x,my=aa.y,ms=aa.s; vis[mx][my][ms]=1; for(int i=0;i<4;i++){ int nx=mx+xx[i],ny=my+yy[i]; if(nx<1 || ny<1 || nx>n || ny>m || (c[nx][ny]>='1' && c[nx][ny]<='9') || c[nx][ny]=='#') continue; //判断该点是否能走 //注意豆豆所在的方格也不能走 int ns=ms; if(i&1) ns=solve(mx,my,nx,ny,ms); //只有在上下走的时候才改变状态，否则状态不变 //如果不能理解也可以写成i==1 || i==3 if(vis[nx][ny][ns]==1) continue; //如果已经更新过，就不再更新 if(f[mx][my][ms]<f[nx][ny][ns]){ f[nx][ny][ns]=f[mx][my][ms]+1; vis[nx][ny][ns]=1; q.push(asd(nx,ny,ns)); } } } for(int i=0;i<mmax;i++){ ans=max(ans,val[i]-f[ii][jj][i]); } } int main(){ scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=d;i++){ scanf("%d",&da[i]); } mmax=1<<d; for(int i=0;i<mmax;i++){ for(int j=1;j<=d;j++){ if(i&(1<<(j-1))) val[i]+=da[j]; } } for(int i=1;i<=n;i++){ scanf("%s",c[i]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]>'0' && c[i][j]<='9'){ int now=c[i][j]-'0'; ax[now]=i,ay[now]=j; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]=='0'){ bfs(i,j); //如果该点为0，就可以作为起点 } } } printf("%d\n",ans); return 0; }SPFA版
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; int n,m,d; int mmax,f[11][11][1<<11],da[11],val[1<<11]; struct asd{ int x,y,s; asd(int aa=0,int bb=0,int cc=0){ x=aa,y=bb,s=cc; } }b[11*11]; char c[11][11]; int xx[4]={0,-1,0,1},yy[4]={-1,0,1,0},ax[12],ay[12]; int ans=-0x3f3f3f3f; int vis[12][12][1<<12]; inline int solve(int mx,int my,int nx,int ny,int ms){ int ns=ms; for(int i=1;i<=d;i++){ if(((mx==ax[i] && nx<ax[i]) || (mx<ax[i] && nx==ax[i])) && ny>ay[i]){ ns^=(1<<(i-1)); } } return ns; } inline void SPFA(int ii,int jj){ queue<asd> q; q.push(asd(ii,jj,0)); memset(f,0x3f,sizeof(f)); f[ii][jj][0]=0; //memset(vis,0,sizeof(vis)); while(!q.empty()){ asd aa=q.front(); q.pop(); int mx=aa.x,my=aa.y,ms=aa.s; vis[mx][my][ms]=0; for(int i=0;i<4;i++){ int nx=mx+xx[i],ny=my+yy[i]; if(nx<1 || ny<1 || nx>n || ny>m || (c[nx][ny]>='1' && c[nx][ny]<='9') || c[nx][ny]=='#') continue; int ns=ms; if(i&1) ns=solve(mx,my,nx,ny,ms); if(f[mx][my][ms]<f[nx][ny][ns]){ f[nx][ny][ns]=f[mx][my][ms]+1; if(vis[nx][ny][ns]==0){ vis[nx][ny][ns]=1; q.push(asd(nx,ny,ns)); } } } } for(int i=0;i<mmax;i++){ ans=max(ans,val[i]-f[ii][jj][i]); } } int main(){ scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=d;i++){ scanf("%d",&da[i]); } mmax=1<<d; for(int i=0;i<mmax;i++){ for(int j=1;j<=d;j++){ if(i&(1<<(j-1))) val[i]+=da[j]; } } for(int i=1;i<=n;i++){ scanf("%s",c[i]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]>'0' && c[i][j]<='9'){ int now=c[i][j]-'0'; ax[now]=i,ay[now]=j; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]=='0'){ SPFA(i,j); } } } printf("%d\n",ans); return 0; }大家一定要注意vis数组的初始化
而且数组不要开太大，否则会T
下面是一个错解，也就是bfs的vis数组没有初始化
#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<cstring> using namespace std; int n,m,d; int mmax,f[11][11][1<<11],da[11],val[1<<11]; struct asd{ int x,y,s; asd(int aa=0,int bb=0,int cc=0){ x=aa,y=bb,s=cc; } };//跑bfs的结构体 char c[11][11]; int xx[4]={0,-1,0,1},yy[4]={-1,0,1,0},ax[11],ay[11]; //xx,yy枚举走的方向，ax,ay记录豆豆的横纵坐标 int ans=-0x3f3f3f3f;//记录最终价值 int vis[11][11][1<<11];//判断该点是否已经遍历过 int solve(int mx,int my,int nx,int ny,int ms){ int ns=ms; for(int i=1;i<=d;i++){ if(((mx==ax[i] && nx<ax[i]) || (mx<ax[i] && nx==ax[i])) && ny>ay[i]){ ns^=(1<<(i-1)); } } return ns; } void bfs(int ii,int jj){ queue<asd> q; q.push(asd(ii,jj,0)); memset(f,0x3f,sizeof(f)); f[ii][jj][0]=0; while(!q.empty()){ asd aa=q.front(); q.pop(); int mx=aa.x,my=aa.y,ms=aa.s; vis[mx][my][ms]=1; for(int i=0;i<4;i++){ int nx=mx+xx[i],ny=my+yy[i]; if(nx<1 || ny<1 || nx>n || ny>m || (c[nx][ny]>='1' && c[nx][ny]<='9') || c[nx][ny]=='#') continue; //判断该点是否能走 //注意豆豆所在的方格也不能走 int ns=ms; if(i&1) ns=solve(mx,my,nx,ny,ms); //只有在上下走的时候才改变状态，否则状态不变 //如果不能理解也可以写成i==1 || i==3 if(vis[nx][ny][ns]==1) continue; //如果已经更新过，就不再更新 if(f[mx][my][ms]<f[nx][ny][ns]){ f[nx][ny][ns]=f[mx][my][ms]+1; if(vis[nx][ny][ns]==0){ vis[nx][ny][ns]=1; q.push(asd(nx,ny,ns)); } } } } for(int i=0;i<mmax;i++){ ans=max(ans,val[i]-f[ii][jj][i]); } } int main(){ scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=d;i++){ scanf("%d",&da[i]); } mmax=1<<d; for(int i=0;i<mmax;i++){ for(int j=1;j<=d;j++){ if(i&(1<<(j-1))) val[i]+=da[j]; } } for(int i=1;i<=n;i++){ scanf("%s",c[i]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]>'0' && c[i][j]<='9'){ int now=c[i][j]-'0'; ax[now]=i,ay[now]=j; } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(c[i][j]=='0'){ bfs(i,j); //如果该点为0，就可以作为起点 } } } printf("%d\n",ans); return 0; }但是令人震惊的是，它竟然能过，而且比正解快10倍，只用70ms
引用pl.er()大佬的思路
它之所以快是因为第一次遍历之后vis数组没有初始化，于是在之后的遍历中它们就不会再进栈
但是这样做显然是错误的，比如下面这组数据
5 5 1 1000 00000 00000 01000 00000 00000正解是992，但是错解却输出990
因此大家一定要注意
15011418730
LV 7
@ 2025-8-24 21:39:08
- 1
