Google Code Jam 2010:Round 2 Problem B. World Cup 2010 large

この前のGCJ2010 Problem BをLarege問題用に書きなおし。
と、言っても、ほとんどContest Analysisの書き写しですが。

前書いたプログラムは、実際の試合順にDPをやってけど、今回は後ろからメモ化再帰。
状態は試合番号とその後観る予定の試合数。

計算量はO(P*2^P)。P=10程度なら余裕で終わるわけですね。うーん、解答書いた人すごい。

#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;

#define rep(i,a,b) for(int i=a;i<b;i++)

using namespace std;


int P;
LL A[1<<11][11];
LL inp[1<<11];

//a:試合番号
//b:試合aのあとに観る予定の試合数
LL dp(int a, int b) {
	LL& r = A[a][b];
	if(r>=0) return r;
	
	if(a>=((1<<P)-1)) {
		//末端ノードの処理
		//試合観戦数が条件をみたしているかチェック
		r = (b>=(P-inp[a])) ? 0 : 1LL<<40;
		return r;
	}
	r = min(
		inp[a] + dp(2*a+1, b+1)+dp(2*a+2, b+1), //a番目の試合を観る
		dp(2*a+1, b) + dp(2*a+2,b));	//a番目の試合を観ない
	return r;
}

int solve(int no)
{
	cin >> P;
	int M = (2<<P)-1;
	rep(i,0,M) {
		cin >> inp[M-1-i];
	}
	memset(A, -1, sizeof(A));
	cout << "Case #" << no << ": " << dp(0,0) << endl;
}

int main()
{
	int T;
	cin >> T;
	rep(no,0,T) {
		solve(no+1);
	}
	return 0;
}