题解 P3638 【[APIO2013]机器人 】
shadowice1984
2018-12-16 11:27:19
我也不知道为什么随手写了一下就抢了这题的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);//拜拜程序~
}
```