UVa11545 Avoiding Jungle in the Dark

問題
http://uva.onlinejudge.org/external/115/11545.html

概要
"S...****................***.D" とかいう感じの道を最短時間で進めという問題。
１マスを１時間で移動することが出来る。
夜は '*' の道を通ることは出来ない。あるマスにいるというのは、そのマスの中の道の最も左端にいるという意味。夜時間（午後6時から午前6時）は '*' を通行することは出来ない。一度あたり最大16時間まで移動することが出来る。一度移動したら 8*n 時間（nは正の整数）は休まないといけない。また道の長さは 2 以上 1000 以下である。

解法
状態（現在位置, 時刻）でDPする。時刻を、現在位置に到達して休憩した後の時刻とすると書きやすいかもしれない。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXL = 1030;
const int REST = 8;

const int INF = 1<<29;

int dp[MAXL+1][24];

int main() {
  
  int Tc; cin >> Tc;
  
  for(int tc=1; tc<=Tc; tc++) {
    string line; cin >> line; const int N = line.size();
    fill(dp[0], dp[MAXL], INF);
    dp[0][6] = 0;
    for(int i=0; i<N; i++) {
      for(int j=0; j<24; j++) {
        for(int k=1; k<=16; k++) {
          bool isDarktime = (j+k)%24 <= 6 || 18 <= (j+k)%24;
          bool isInJungle = line[i+k] == '*';
          if(isDarktime && isInJungle) break;
          
          for(int l=1; l<3; l++) {
            isDarktime = (j+k+REST*l)%24 <= 6 || 18 <= (j+k+REST*l)%24;
            if(isInJungle && isDarktime) break;
            dp[i+k][(j+k+REST*l)%24]
                = min(dp[i+k][(j+k+REST*l)%24], dp[i][j]+(k+REST*l));
          }
        }
      }
    }
    
    cout << "Case #" << tc << ": ";
    
    int ans = *min_element(dp[N-1], dp[N])-REST;
    if(ans >= INF-REST) cout << -1 << endl;
    else cout << ans << endl;
  }
  
  return 0;
}