読者です 読者をやめる 読者になる 読者になる

DPコンテスト J:ボール

一番左はじのボールの、一つ右めがけて投げ続ければよい
ボールの座標が3,8,10ならば4に投げ続け、3が倒れたら9へ投げ続ける
ソートをするのでO(nlogn)
邪悪なコードになったが、どうやらO(2^n)のコードが簡単だとか

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>

using namespace std;
typedef long long ll;

int n;
static double dp[4][16];
static bool flag[4][16];
int x[16];

double solve(int f, int t) {
	if (flag[f][t]) return dp[f][t];
	if (t >= n) return 0;
	if (t == n-1) return 3;
	if (t == n-2) {
		if (f) {
			return 3;
		}
		if (x[n-1] - x[n-2] > 2) {
			return 6;
		} else {
			return 4.5;
		}
	}
	double p = 0;
	int d = 0;
	switch (f) {
		case 0:
			p += solve(0, t+1);
			break;
		case 1:
			p += solve(0, t+2);
			break;
		case 2:
			p += solve(1, t+1);
			break;
		case 3:
			p += solve(0, t+3);
			break;
	}
	bool b = false;
	if (x[t+1] - x[t] == 1) b = true;
	switch (f) {
		case 0:
			if (b) {
				p += solve(1, t);
			} else {
				d++;
			}
			break;
		case 1:
			d++;
			break;
		case 2:
			p += solve(3, t);
			break;
		case 3:
			d++;
			break;
	}
	bool b1 = false, b2 = false;
	if (x[t+1] - x[t] == 2) b1 = true;
	if (x[t+2] - x[t] == 2) b2 = true;
	switch (f) {
		case 0:
			if (b1) {
				p += solve(1, t);
			} else if (b2) {
				p += solve(2, t);
			} else {
				d++;
			}
			break;
		case 1:
			if (b2) {
				p += solve(3, t);
			} else {
				d++;
			}
			break;
		case 2:
			d++;
			break;
		case 3:
			d++;
			break;
	}
	switch (d) {
		case 0:
			p /= 3;
			p += 1;
			break;
		case 1:
			p /= 2;
			p += 1.5;
			break;
		case 2:
			p += 3;
	}
	dp[f][t] = p;
	return p;
}

int main() {
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		x[i] = v[i];
	}
	printf("%.10f\n", solve(0, 0));
	return 0;
}