Luogu P3638 [APIO2013]机器人

标签：pre   printf   cpp   pop   turn   else   line   puts   size   

（类似）斯坦纳树+DP

\(f[l][r][i][j]\) 表示已经构成 \([l,r]\) 的机器人，并在点 \((i,j)\) 的最小代价。

预处理出 \(d[i][j][k]\) 表示在点 \((i,j)\) 方向为 \(k\) 时最终能够到达的点。

\(f[l][r][i][j]=\min(f[l][k][i][j],f[k+1][r][i][j])\)

\(枚举k,f[l][r][X][Y]=\min(f[l][r][X][Y],f[l][r][i][j]+1),(X,Y)表示(i,j,k)最终到达的点\)

spfa 要优化：用两个队列，一个存初始状态（先排完序再扔进去），一个存扩展出来的状态，每次取两个队头中较小的去扩展。

#include
#include
#include
#include
#include
#include
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
  register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
  do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=10,M=510,Inf=0x3f3f3f3f;
const int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
struct node { int x,y,dis;
    inline bool operator h||jw) return 0;
  if(s[i][j]=='x') return 0;
  if(d[i][j][k]) return d[i][j][k];
  if(vis[i][j][k]) return -1;
  vis[i][j][k]=true; R K=k;
  if(s[i][j]=='A') K=(k+1)%4;
  if(s[i][j]=='C') K=(k+3)%4;
    d[i][j][k]=dfs(i+dx[K],j+dy[K],K);
  if(!d[i][j][k]) d[i][j][k]=P(i,j);
  vis[i][j][k]=false;
  return d[i][j][k];
}
queue q1,q2;
vector mem;
inline void main() {
  n=g(),w=g(),h=g();
  for(R i=1;i=1;--l) for(R r=l;rf[l][r][x][y]+1) {
          f[l][r][xx][yy]=f[l][r][x][y]+1;
          if(!inq[xx][yy]) {
            q2.push((node){xx,yy,f[l][r][xx][yy]});
            inq[xx][yy]=true;
          }
        }
      }
    }
  }
  for(R i=1;i

2020.01.18

Luogu P3638 [APIO2013]机器人

标签：pre   printf   cpp   pop   turn   else   line   puts   size   

原文地址：https://www.cnblogs.com/Jackpei/p/12209865.html