POJ 3404 Bridge over a rough river

問題

N人が橋を渡りたい。
橋は同時に2人までしか渡ることができず、また一つしかない懐中電灯を持って渡る必要がある。
それぞれの人に対して橋を渡るのにかかる時間が決まっている。
二人が同時に渡るときは遅い人に合わせる。

全員が橋を渡り終えるのにかかる時間を求めよ。

制約条件

N≦50

方針

dp[i][j]を、懐中電灯は橋のこちら側にあるとして、

• iが0: 2番目に早い人が橋のこちら側にいる 1: 2番目に早い人が橋の向こう側に居る
• j番目より遅い人が全て渡り終わっている

のにかかる最短の時間とする。

これを更新するようなDPで解ける。

DPの状態遷移は、二番目に早い人がこちらにいるときは、
「二番目に早い人が、一番早い人と向こう側へ行く」選択肢しかなく
二番目に早い人が向こう側にいるときは、
「一番早い人と一番遅い人が向こう側へいき、二番目に早い人が懐中電灯を持ち帰る」または
「一番遅い人と一番早い人が一緒に向こう側へ行き、一番早い人が懐中電灯を持ち帰る」
が考えられる。

ソースコード

int N,t[50];

int dp[2][50];
int rec(int sec,int last){
  if(dp[sec][last]>=0)return dp[sec][last];
  int &ret=dp[sec][last];
  
  if(last<=1)return last==0||sec?t[0]:t[1];
  if(last==2&&sec)return t[2];
  
  ret=(int)1e9;
  if(sec==0){
    ret=min(ret,rec(1,last)+t[0]+t[1]);
  }
  else{
    if(last>2)ret=min(ret,rec(0,last-2)+t[last]+t[1]);
    ret=min(ret,rec(1,last-1)+t[last]+t[0]);
  }
  return ret;
}
int main(){
  scanf("%d",&N);
  rep(i,N)scanf("%d",t+i);
  sort(t,t+N);
  
  if(N<=2){
    printf("%d\n",N==1?t[0]:t[1]);
    return 0;
  }
  
  memset(dp,-1,sizeof(dp));
  printf("%d\n",rec(0,N-1));
  
  return 0;
}