SRM 513 Div2 Hard CutTheNumbers

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11501&rd=14538
N*Mの盤面に0~9の数字が書かれている。この盤面を垂直方向か、水平方向の断片に分ける（問題文中の図参照）。この断片一つ一つを、垂直な断片なら上から、水平な断片なら左から10進数の数字として読んだ数字を、その断片の得点とする。得点を最大化するような断片化を行った時の得点を求めよ。

N,M ≦ 4

やりかた

Editorialを参考にしました。

といっても、制約が小さいのであるセルを縦断片に含めるか、横断片に含めるか全状態を列挙して得点を求め、最大値を計算するだけ。

以下ソース。

class CutTheNumbers {
public:
  int maximumSum(vector <string> board) {
    int result = 0;
    int N = board.size();
    int M = board[0].size();

    bool used[N][M];
    for(int i = 0; i < (1 << (N * M)); i++){
      
      int point = 0;
      memset(used, false, sizeof(used));
      for(int y = 0; y < N; y++){
	for(int x = 0; x < M; x++){
	  if(((i >> (y * M + x)) & 1) && !used[y][x]){
	    int t = 0;
	    for(int k = 0; (i >> (y * M + x + k) & 1) && x + k < M; k++){
	      t *= 10;
	      t += (board[y][x + k] - '0');
	      used[y][x + k] = true;
	    }
	    point += t;
	  }
	  if(!((i >> (y * M + x)) & 1) && !used[y][x]){
	    int t = 0;
	    for(int k = 0; !(i >> ((y + k) * M + x) & 1) && y + k < N; k++){
	      t *= 10;
	      t += (board[y + k][x] - '0');
	      used[y + k][x] = true;
	    }
	    point += t;
	  }
	}
      }
      result = max(result, point);
    }
    return result;
  }
};

今となってはなんで解けなかったのか一切わからない。何一つ難しいことないのに。