提出 #1624811

---

ソースコード 拡げる

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define pb push_back
using namespace std;

typedef vector<int> vi;

int N;
double dp[1<<13];
double P[14][3];
int a[14];
double sub[1<<13][8];

int main() {
	cin >> N;

	rep(i, N) {
		cin >> a[i];
		if (i > 0) {
			rep(j, 3) {
				cin >> P[i][j];
				P[i][j] /= 100;
			}
		}
	}

	rep(i, 1 << (N-1)) {
		if (i == 0) continue;

		vector<double> pp[N+1];
		rep(i, N+1) pp[i].resize(8);
		pp[0][0] = 1.0;

		rep(j, N-1) {
			if ((i>>j)&1) {
				rep(k, 8) {
					rep(u, 3) {
						pp[j+1][k | (1 << u)] += pp[j][k] * P[j+1][u];
					}
				}
			} else {
				rep(k, 8) {
					pp[j+1][k] = pp[j][k];
				}
			}
		}
		rep(k, 8) {
			sub[i][k] = pp[N-1][k];
		}
	}

	dp[0] = 1.0;
	for (int i = 1; i < (1<<(N-1)); ++i) {
		double mx = 0.0;
		bool f = 1;

		rep(j, N-1) {
			if ((i>>j)&1) {
				if (a[j+1] > a[0]) {
					f = 0;
				}
			}
		}

		rep(c, 3) {
			double t = 0.0;

			for (int j = i; j >= 0; --j) {
				j &= i;
				double p = 1.0;
				rep(k, N-1) {
					if ((i>>k) & 1) {
						if ((j>>k) & 1) {
							p *= P[k+1][c];
						} else {
							p *= P[k+1][(c+2)%3];
						}
					}
				}
				p *= dp[j];
				t += p;
			}

			if (f) {
				rep(l, 8) {
					int b = (1 << c) | l;
					int bit = __builtin_popcount(b);
					if (bit == 1 || bit == 3) {
						t += sub[i][l];
					}
				}
			}

			mx = max(mx, t);
		}
		dp[i] = mx;
	}

	printf("%.8f\n", dp[(1<<(N-1))-1]);

	return 0;
}

提出情報

ジャッジ結果