アルゴリズム別テンプレート - yanprog @ ウィキ

メモ化再帰

int memo[100];
 
int func(int n){
  assert(0<=n && n<100);
  int &ret=memo[n];
  if(ret!=-1){
    return ret;
  }
 
  if(n==0 || n==1)return ret=1;
  return ret=func(n-1)+func(n-2);
}
 
nclr(memo);
 
 
 

尺取法

// min(x2) such that P(x1,x2)
int x1=0, x2=0;
while(1){
  while(x2<N && !P(x1,x2)){
    x2++;
    if(x2>=N)break;
    updata P;
  }
  if(x2>=N)break;
  do ; // P(x1,x2) here
  x1++;
  if(x1>=N)break;
  updata P;
}
 
// max(x2) such that P(x1,x2)
int x1=0,x2=0;
while(1){
  while(x2+1<N && P(x1,x2+1)){
    x2++;
    updata P;
  }
  do ; // P(x1,x2) here
  x1++;
  if(x1>=N)break;
  updata P;
}
 
 
 

bfs

typedef pair<int,int> ;
queue<P> que;
que.push(P(0,s));
int d[1000];
 
nclr(d);
while(que.size()){
  P p=que.front();que.pop();
  int v=p.first;
  int pos=p.second;
  if(m[pos]=='#')continue;
  if(d[pos]==-1)continue;
  d[pos]=v;
  EACH(pnei,edge[pos]){
    que.push(P(*pnei, v+1));
  }
}