静かで孤独な日記

のんびりたまに

AOJ 2237 The Castle

#include<bits/stdc++.h>
using namespace std;

int n,m;
double dp[(1<<16)][17];
double a[20][20];

double memo(int state,int enemy){
	if(enemy==m)return 1;
	if(state==(1<<n)-1)return 0;
	if(dp[state][enemy]>=0)return dp[state][enemy];
	double &res=dp[state][enemy];
	res=0;
	for(int i=0;i<n;i++){
		if(state&(1<<i))continue;
		double now=1,sum=0;
		for(int j=enemy;j<m;j++){
			sum+=now*(1-a[i][j])*memo((state|(1<<i)),j);
			now*=a[i][j];
		}
		sum+=now;
		res=max(res,sum);
	}
	return dp[state][enemy];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout<<fixed;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<(1<<16);i++)
	  for(int j=0;j<17;j++)
	  	dp[i][j]=-1;
	cout<<memo(0,0)<<endl;
	return 0;
}
  • ループでdpやって答えが合わなかったから、メモ化再帰でやりました。
  • stateは死んだら1、生きてたら0です。
  • 最適に行動したいので、どの猫がいつ死んで次にどの猫を戦わせれば良いかを知っておく必要がある。
  • んー、難しいですね。
  • 下のリンクは公式解説スライドです。