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; }