UVa 1099 : Sharing Chocolate - 土下座しながら探索中

問題リンク：http://uva.onlinejudge.org/external/10/1099.html

問題概要：
n人の人とh*wのチョコレートが存在する
n人がそれぞれa[i]個(1<= i <= n)のチョコレートのピースを要求している
チョコレートを縦または横に割る動作だけでn人の全ての要求するピースをつくる亊ができるかどうか判定せよ

制約：
・ 1 <= n <= 15
・ 1 <= h,w <= 100

解法：
メモ化再帰で解いた
最初に要求されるピースの総和がh*wとならない場合は再帰せずにNoとする

memo[(1<<15)][101] という配列を用意する
(1<<15) はもう既に作ったピースa[i]の情報ををビットとしたもの
i番目のビットが1がならばa[i]はすでに作ったとし、０ならばまだ作っていないものとする
101は今みているチョコレートのx軸方向の長さを表す
この配列にはその状態が作成可能かどうかを入れておく

再帰は以下の２つの引数を持って行う

bool rec(int state,int x);

stateはどの要求を満たしたかをビットとしてもったもの
xは今みているチョコレートのx軸方向の長さ
今みているチョコレートのy軸方向の長さは引数とする必要はない
stateとxがあれば復元できるからである

sum = 0;
for i 0..n-1
  if (state>>i) & i 
    sum += a[i];

とすればstateでのチョコレートの面積が分かるので
それをxで割ればyの長さがわかる
同様の理由でメモ化の配列も2次元までしかない

最初に引数として持ってくxはhかwを適当に選択する
どちらをxとしてもyはそれに対応する長さになるので問題ではない

再帰で次の状態に遷移する際に、
分割したチョコレートの面積が今のチョコレートのxまたはyで割りきれたのであれば再度再帰を利用してチェックする
割り切れない場合は垂直または平行にカットできない

stateのたっているビットが１つになったのであれば
割りきれたという亊なのでtrueをかえす

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 16

using namespace std;

int n,h,w;
vector<int> cut;
int sum[(1<<MAX)];
char memo[(1<<MAX)][101];

char rec(int state,int len)
{
  if(memo[state][len] != '-')return memo[state][len];

  if(__builtin_popcount(state) == 1)
    {
      return memo[state][len] = 'o';
    }

  int x = len, y = sum[state] / len;

  for(int next_state=state&(state-1);next_state;next_state=state&(next_state-1))
    {
      int diff = state - next_state;

      if(sum[diff]%x==0 && rec(next_state,min(x,sum[next_state]/x)) == 'o' && rec(diff,min(x,sum[diff]/x)) == 'o'  )
	{
	  return memo[state][len] = 'o';
	}

      if(sum[diff]%y==0 && rec(next_state,min(y,sum[next_state]/y)) == 'o' && rec(diff,min(y,sum[diff]/y)) == 'o' )
	{
	  return memo[state][len] = 'o';
	}

    }

  return memo[state][len] = 'x';

}

int main()
{
  int CNT = 1;
  while(scanf("%d",&n),n!=0)
    {
      cut.resize(n);

      scanf("%d %d",&h,&w);
      rep(i,n)
	{
	  scanf("%d",&cut[i]);
	}

      rep(i,(1<<n))
	{
	  sum[i] = 0;
	  rep(j,n)
	    {
	      if((i>>j) & 1)
		{
		  sum[i] += cut[j];
		}
	    }
	  rep(j,101)memo[i][j] = '-';
	}

      printf("Case %d: ",CNT++);
      if(h*w != sum[(1<<n)-1])
	{
	  puts("No");
	  continue;
	}
      char res = rec((1<<n)-1,min(h,w));
      if(res == 'o')puts("Yes");
      else   puts("No");

    }
  return 0;
}