TopCoder SRM 343 Div1 Medium MoneyGame

問題

3種類の硬貨があり、それぞれの価値はvalue[i]である。
先手がi枚目のコインをlennysCoins[i]枚もって、
後手がi枚目のコインをfredsCoins[i]枚もって、次のようなゲームを行う。

  • ポットに手持ちから一枚コインを入れる
  • 入れたコインの価値より小さい額のコインをポットから取り出す
  • コインを入れられなくなったプレイヤーの負け
  • 負けたプレイヤーは、その時点で相手が持っているお金の総額だけ負ける


お互いが最善を尽くすとき、先手は最大でどれだけの金額勝てるか(負けるなら損を最小に)求めよ。
勝ちの場合はその金額を、負けの場合はその金額にマイナスを付けて返せ。

制約条件

コインは3種類
lennysCoins[i],fredsCoins[i]≦5
value[i]≦1000

方針

手番のプレイヤーの手持ちのお金は常に減るため、ゲームは必ず終了する。
したがって、min-max探索をすればよい。


探索のメモにmapを使うとTLE.
配列に詰め込んだら通った。

ソースコード

vi val;
const int MX=11*11*11*11*11*11*2;
int dp[MX];
inline int pack(const vi &v,int t){
	int res=0;
	rep(i,6)res*=11, res+=v[i];
	return res*2+t;
}
int rec(vi coin,int turn){
	if(dp[pack(coin,turn)]!=inf)return dp[pack(coin,turn)];
	
	int ans=-inf, enemy=0, lose=1;
	rep(i,3)enemy+=val[i]*coin[i+(1-turn)*3];
	
	rep(i,3)if(coin[i+turn*3]){
		lose=0;
		coin[i+turn*3]--; coin[i+6]++;
		rep(a,coin[6]+1)rep(b,coin[7]+1)rep(c,coin[8]+1){
			int sum=a*val[0]+b*val[1]+c*val[2];
			if(sum>=val[i])continue;
			coin[6]-=a; coin[7]-=b; coin[8]-=c;
			coin[turn*3]+=a; coin[turn*3+1]+=b; coin[turn*3+2]+=c;
			ans=max(ans,-rec(coin,1-turn));
			coin[turn*3]-=a; coin[turn*3+1]-=b; coin[turn*3+2]-=c;
			coin[6]+=a; coin[7]+=b; coin[8]+=c;
		}
		coin[i+turn*3]++; coin[i+6]--;
	}
	if(lose)ans=-enemy;
	return dp[pack(coin,turn)]=ans;
}
class MoneyGame {
	public:
	int play(vector <int> lennysCoins, vector <int> fredsCoins, vector <int> values) 
	{
		val=values;
		rep(i,MX)dp[i]=inf;
		vi coin;
		rep(i,3)coin.pb(lennysCoins[i]);
		rep(i,3)coin.pb(fredsCoins[i]);
		rep(i,3)coin.pb(0);
		return rec(coin,0);
	}
};