题解 P3638 【[APIO2013]机器人 】

我也不知道为什么随手写了一下就抢了这题的rk1…… ~~拒绝stl的队列从我做起~~ 为了方便起见我们认为$(-1,0),(0,1),(1,0),(0,-1)$这四个方向的标号分别为$0,1,2,3$ 首先我们设$dp(i,j,k)$ 表示在$i,j$点按照k这个方向踹一脚机器人这个机器人会跑到什么地方去 那么这个东西还是比较好转移的，直接递归下去记忆化搜索就可以了 但是我们可能需要注意两个点，第一点就是如果$(i+dx(k),j+dy(k))$这个点是墙或者障碍物的话我们需要将$dp(i,j,k)$设为$num(i,j)$意思就是说这个机器人不会动了 另外一点就是环，我们在记忆化搜索的时候记录一下什么状态被压在了栈里，如果我们发现我们访问了一个栈内的元素,那么将这个栈内的元素的dp值置为$-1$，注意这里一定要和墙的标号区别开，不然会导致一些奇奇怪怪的错误 好了那么假设我们处理出了这个dp数组，现在我们就可以建出一张图来了~ 然后我们发现这个问题十分的像斯坦纳树问题，只是我们不是状压dp而是区间dp了 具体点来讲我们设$dp(i,j,k)$表示$(i,j)$这个复合机器人出现在$k$点的最小代价 那么层外转移就是向区间dp一样的枚举分割点mid进行转移 $$dp(i,j,k)=\min_{mid=l}^{r-1}(dp(i,mid,k)+dp(mid+1,r,k))$$ 然后层内的转移我们发现似乎满足三角不等式(其中$k.alist$表示点k的出边集合) $$dp(i,j,k) \leq min_{v\in k.alist}dp(i,j,v)+1$$ 不过此时似乎转移是带环的…… 那么一般斯坦树的套路就是用spfa进行转移…… 不过这里不知道为什么spfa会tle，所以我们需要一些比较nb一点的剪枝，不然过不去 具体点来讲我们开两个队列，一个存一开始的点，并且这个队列中点是排好序的，排序这里建议手写计数排序，会快一点，另一个队列存需要去松弛别的点的点 然后每次取队头的时候去两个点中dis值较小的那个去松弛，加上这个玄学剪枝之后我们的spfa就跑的飞起了，然后就不用担心tle了~ 然后这题并没有你想的那么毒瘤，注意实现方式的话还是很好写的~ 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=520;const int E=4*1e6+10;const int M=12; int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1}; bool book[N][N][4];int dp[N][N][4];int tr[N][N];int ctt;int n;int w;int h; int v[4*N*N];int x[4*N*N];int ct;int al[N*N];char mp[N][N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} inline int dfs(const int& x,const int& y,const int& tw)//记忆化搜索 { if(book[x][y][tw]){return dp[x][y][tw]=-1;} if(dp[x][y][tw]!=-2)return dp[x][y][tw]; book[x][y][tw]=true;int tx=x+dx[tw];int ty=y+dy[tw]; switch(mp[tx][ty]) { case 'x':{dp[x][y][tw]=tr[x][y];break;} case 'A':{dp[x][y][tw]=dfs(tx,ty,(tw+3)%4);break;} case 'C':{dp[x][y][tw]=dfs(tx,ty,(tw+1)%4);break;} default:{dp[x][y][tw]=dfs(tx,ty,tw);break;} }book[x][y][tw]=false;return dp[x][y][tw]; }int sum[N*N];int q1[N*N];int q2[E];bool inq[N*N];int hd;int tl;int dis[M][M][N*N]; inline void rixs(int* dis)//计数排序 { int mx=0;for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)mx=max(mx,dis[i]); for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)sum[dis[i]]++; for(int i=1;i<=mx;i++)sum[i]+=sum[i-1]; for(int i=ctt;i>=1;i--)if(dis[i]<0x3f3f3f3f)q1[sum[dis[i]]--]=i; for(int i=1;i<=ctt;i++)if(dis[i]<0x3f3f3f3f)inq[i]=true; for(int i=0;i<=mx;i++)sum[i]=0; } inline void ex_spfa(int* dis)//spfa { rixs(dis);int cur=1;int hd=1;int tl=0; while((cur<=ctt)||(hd<=tl)) { int nw=0x3f3f3f3f; if((cur<=ctt)&&(hd>tl||dis[q1[cur]]<=dis[q2[hd]]))nw=q1[cur],cur++; else nw=q2[hd],hd++;inq[nw]=false; for(int i=al[nw];i;i=x[i]) if(dis[v[i]]>dis[nw]+1){dis[v[i]]=dis[nw]+1;if(!inq[v[i]])inq[v[i]]=true,q2[++tl]=v[i];} } } int main() { scanf("%d%d%d",&n,&w,&h); for(int i=1;i<=h;i++)scanf("%s",mp[i]+1); for(int i=1;i<=h;i++)//各种初始化~ for(int j=1;j<=w;j++)if(mp[i][j]!='x')tr[i][j]=++ctt; for(int j=0;j<=w+1;j++)mp[0][j]='x';for(int j=0;j<=w+1;j++)mp[h+1][j]='x'; for(int i=0;i<=h+1;i++)mp[i][0]='x';for(int i=0;i<=h+1;i++)mp[i][w+1]='x'; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++)for(int k=0;k<4;k++)dp[i][j][k]=-2; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++)if(mp[i][j]!='x')for(int k=0;k<4;k++)dfs(i,j,k); for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) if(mp[i][j]!='x')for(int k=0;k<4;k++) if(dp[i][j][k]!=-1&&dp[i][j][k]!=tr[i][j])add(tr[i][j],dp[i][j][k]); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++)for(int k=1;k<=ctt;k++)dis[i][j][k]=0x3f3f3f3f; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) if('0'<mp[i][j]&&mp[i][j]<='9'){int t=mp[i][j]-'0';dis[t][t][tr[i][j]]=0;} for(int len=1;len<=n;len++) for(int l=1,r=l+len-1;r<=n;l++,r++)//dp { for(int mid=l;mid<r;mid++) for(int k=1;k<=ctt;k++)dis[l][r][k]=min(dis[l][r][k],dis[l][mid][k]+dis[mid+1][r][k]); ex_spfa(dis[l][r]); }int ans=0x3f3f3f3f; for(int i=1;i<=ctt;i++)ans=min(ans,dis[1][n][i]);printf("%d",(ans==0x3f3f3f3f)?-1:ans);//拜拜程序~ } ```