题解 P5003 【跳舞的线 - 乱拐弯】

Imakf · 2018-11-05 13:20:13 · 题解

几万年前出的题目，当时在邀请赛中出的，然后因为宣传邀请赛被禁言了。

这里只讲max的求法，因为min与max求法类似！实在不懂可以私信

10 pts puts("-1");

没什么好说的吧，这个分给的很良心的，虽然这道题巨水

10 pts dfs爆搜

void dfs(int x,int y,bool fac,int step){
  if(x>n||y>m|| 此处有障碍 ) return ;
  //x,y表示当前位置，step表示步数，fac表示方向 (0为向右，1为向下)
  if(x==n&&y==m){
    ans=max(ans,step);
      return 0;
  }
  if(fac==0){
      dfs(x,y+1,fac,step);
      dfs(x+1,y,fac^1,step+1);
  }
  else{
      dfs(x+1,y,fac,step);
      dfs(x,y+1,fac^1,step)
  }

}

不剪枝的搜索必然拿不到高分啦

50 pts dfs加个记忆化

void dfs(int x,int y,bool fac,int step){
  if(x>n||y>m|| 此处有障碍 ) return ;
  if(dis[u][v]>cans)    return; //jiyihua
  dis[u][v]=max(dis[u][v],cans);    //jiyihua
  if(fac==0){
      dfs(x,y+1,fac,step);
      dfs(x+1,y,fac^1,step+1);
  }
  else{
      dfs(x+1,y,fac,step);
      dfs(x,y+1,fac^1,step)
  }

}

50pts bfs

不讲了，写起来很简单

100pts~~Dp

这道题是在2017NOIP之前出的，当时我是个小蒟蒻鸭（现在还是），不会dp，然后一年之后我再来做了这道题，然后把数据加强了QAQ