教育房地产 网站建设,望野拼音,建立收费网站,用dw设计网站模板下载[SCOI2009]围豆豆 \(n\times m(n,m\le 10)\) 的网格中有 \(d\) 个球 \((d\le 9)\)#xff0c;要求在网格中选定一个起点开始做一个欧拉回路#xff0c;路径的价值为路径完全包住的球的价值之和减去路径长度#xff0c;求所有路径中的价值最大值。 有价值与步数的两个限制要求在网格中选定一个起点开始做一个欧拉回路路径的价值为路径完全包住的球的价值之和减去路径长度求所有路径中的价值最大值。 有价值与步数的两个限制首先想着把其中一个作为状态控制变量。 由于起点关系回程所以 \(\bigstar\texttt{important}\)枚举起点寻找答案。 控制了起点和状态容易想到设 \(dp(i,j,state)\) 表示从起点到坐标为 \((i,j)\) 的点且这半条路径包含的点的集合为 \(state\) 时的最小步数。 \(\uparrow\) 因为路径是一个多边形用计算几何的方法判断每个点是否在多边形内部即从这个点向左侧做射线进过边的数量为奇数时在内部。(由于这是网格所以特殊情况时如果这条线断平行则不计算不平行则计算)。 之后用上边的 \(dp\) 直接暴力 bfs 即可。 $\texttt{code}$ #define Maxn 15
#define Maxsta 1005
int n,m,d,ans;
int v[Maxn],ax[Maxn],ay[Maxn],ds[Maxn][Maxn][Maxsta];
int zou[4][2]{{1,0},{-1,0},{0,1},{0,-1}};
char mp[Maxn][Maxn];
struct Dot { int x,y,State,ds; };
inline int calc(int sx,int sy,int tx,int ret)
{for(int i1;id;i){if((sxax[i] txax[i] syay[i]) || (sxax[i] txax[i] syay[i]))ret^1(i-1);}return ret;
}
inline int Count(int State)
{int ret0;for(int i1;id;i) if(State (1(i-1))) retv[i];return ret;
}
void bfs(int sx,int sy)
{memset(ds,0x3f,sizeof(ds)),ds[sx][sy][0]0;queueDot q; q.push((Dot){sx,sy,0,0});while(!q.empty()){Dot curq.front(); q.pop();for(int i0,nx,ny,ns;i4;i){nxcur.xzou[i][0],nycur.yzou[i][1];if(nx1 || nxn || ny1 || nym || mp[nx][ny]!0)continue;nscalc(cur.x,cur.y,nx,cur.State);if(ds[nx][ny][ns]!inf) continue;ds[nx][ny][ns]cur.ds1;q.push((Dot){nx,ny,ns,ds[nx][ny][ns]});}}
}
int main()
{nrd(),mrd(),drd();for(int i1;id;i) v[i]rd();for(int i1;in;i) scanf(%s,mp[i]1);for(int i1,num;in;i) for(int j1;jm;j)if(isdigit(mp[i][j]))nummp[i][j]-48,ax[num]i,ay[num]j;for(int i1;in;i) for(int j1;jm;j){bfs(i,j);for(int k(1d)-1;k0;k--)ansmax(ans,Count(k)-ds[i][j][k]);}printf(%d\n,ans);return 0;
}
