Typical DP Contest J - ボール

問題文 : ボール

解法 :
$dp[S]$ : 物の集合$S$ を倒すのにかかるコストの期待値, とすると, すべての$i$ について
$dp[S] = \min \left( \dfrac{1}{3}dp[S - \{i\}] + \dfrac{1}{3}dp[S - \{i - 1\}] + \dfrac{1}{3}dp[S - \{i + 1\}] + 1 \right )$

となるから, これをビットDP などで求めれば良い. $S = S - \{i\}$ となる様な場合は適切に移項などをすることで処理する.

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

double dp[1 << 16];

double getProb(int bits)
{
	if (bits == 0) return (0);
	else if (dp[bits] >= 0) return (dp[bits]);
	
	double mini = 1e18;
	
	for (int i = 0; i < 16; i++){
		int cnt = 0;
		double prob = 1;
		if ((bits >> i & 1) || (bits >> (i - 1) & 1) || (bits >> (i + 1) & 1)){
			
			if (((bits >> i) & 1) != 0){
				prob += getProb(bits ^ (1 << i)) / 3;
			}
			else cnt++;
			
			if (i && ((bits >> (i - 1)) & 1) != 0){
				prob += getProb(bits ^ (1 << (i - 1))) / 3;
			}
			else cnt++;
			
			if (((bits >> (i + 1)) & 1) != 0){
				prob += getProb(bits ^ (1 << (i + 1))) / 3;
			}
			else cnt++;
			
			if (cnt == 1) prob = prob * 1.5;
			else if (cnt == 2) prob *= 3;
			mini = min(mini, prob);
		}
	}
	
	return (dp[bits] = mini);
}

int main()
{
	int N;
	
	scanf("%d", &N);
	
	int bits = 0;
	
	for (int i = 0; i < 1 << 16; i++) dp[i] = -1;
	
	for (int i = 0; i < N; i++){
		int x;
		scanf("%d", &x);
		bits |= (1 << x);
	}
	
	printf("%lf\n", getProb(bits));
	
	return (0);
}