はやし屋

競技プログラミングのメモ きたない

AOJ 0581: Gifts

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581

逆にしてdpするのが良いと思って実装したが、既に訪れたとこどう管理するかわからなかったので、公式解説を見た。
http://www.ioi-jp.org/joi/2012/2013-yo/2013-yo-t6/review/2013-yo-t6-review.html
"許される寄り道の回数が最も大きい K = 3 の場合でも,前述の条件を満たす区画は最大でも 12 個しかない."
思いつかないですね...

forで書くとヤバそうだったのでメモ化再帰しました

#include<iostream>
#include<algorithm>
using namespace std;
  
#define rep(i,n) for(int i = 0 ; i < n ; ++i)
  
  
int dp[1<<12][54][54][4];
int h , w , k;
string st[54];
  
int dy[] = {0,-1,0,1};
int dx[] = {-1,0,1,0};
  
bool isover(int y , int x){
  return (y < 0 || x < 0 || x >= w || y >= h);
}
// ←↑こす0
  
// new , old
 
// 訪れたことがあるか
bool judge(int bit){
  int ny = 0 , nx = 0 ;
  for(int i = 0 ; i < 6 ; ++i , bit >>= 2){
    int dir = bit%4;
    ny += dy[dir] , nx += dx[dir];
    if(ny == 0 && nx == 0)return true;
  }
  return false;
}
  
int getMax(int y , int x , int sur , int bit){
  if(y == 0 && x == 0)return 0;
  
  if(dp[bit][y][x][sur] != -1 << 28)return dp[bit][y][x][sur];
  
  int vis = 0  , ret = -1 << 28;
  if(st[y][x] != '.' && !judge(bit))vis = st[y][x] - '0'; 
  
  for(int i = 0 ; i < 4 ; ++i){
    int nx = x + dx[i] , ny = y + dy[i];
    if(!isover(ny,nx)){
      if(st[ny][nx] != '#'){
	if(sur - (i>=2) >= 0){
	  ret = max(ret,getMax(ny,nx,sur-(i>=2),((1<<12)-1)&((bit<<2)+i)) + vis);
	}
      }
    }
  }
  
  return dp[bit][y][x][sur] = ret;
}
  
int main(){
  cin >> h >> w >> k;
  for(int i = 0 ; i < h ; ++i){
    cin >> st[i];
  }
  for(int i = 0 ; i < 1 << 12 ; ++i){
    for(int y = 0 ; y < 54 ; ++y){
      for(int x = 0 ; x < 54 ; ++x){
	for(int k = 0 ; k < 4 ; ++k){
	  dp[i][y][x][k] = -1 << 28;
	}
      }
    }
  }
  
    
  int ret = getMax(h-1,w-1,k,0);
  cout << ret << endl;
}