AOJ 2434 Audition

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434）

制約条件

n≦2000
m≦2000

方針

ビジュアル、ダンス、ヴォーカルそれぞれにi回のアピールをしたときに
得られるオーディションポイントの期待値の最大値をe[type][i]とする。

すると、求めるものはmax{e[0][i] + e[1][j] + e[2][k] | i + j + k = m}

e[type][i]はそれぞれ独立に求められる。
i回アピールしたときに、j番目の人に勝つ確率は、
確率の累積和を計算しておけば簡単に求められる。

dp[k]で、主人公がk位になる確率を求めるのだが、
上位3番までにしかポイントはつかないので、テーブルを3まで持てばよい。

最下位になる確率は全部に負ける確率をかけたもの。
確率が求まれば、期待値が求まる。

ソースコード

int n, m, a[2000], b[2000], c[2000];
double sum[2010], e[3][2010], dp[4][2010];

void calc(double *e, int *v, int bonus){
	rep(i, m + 1){
		double dp[4] = {}, p = 1;
		dp[0] = 1;
		for(int j = 1; j < n; j++){
			int need = (v[0] * i + v[j] - 1) / v[j] - 1;
			double w = need < 0 ? 0 : sum[min(m, need)];
			
			p *= 1 - w;
			for(int k = 2; k >= 0; k--){
				dp[k + 1] += dp[k] * (1 - w);
				dp[k] *= w;
			}
		}
		e[i] = (dp[0] + dp[1] + dp[2]) * bonus - p;
	}
}

int main(){
	cin >> n >> m;
	sum[0] = 1;
	rep(i, m) for(int j = i; j >= 0; j--){
		sum[j + 1] += sum[j] / 3;
		sum[j] *= 2 / 3.0;
	}
	rep(i, m) sum[i + 1] += sum[i];
	
	rep(i, n) cin >> a[i] >> b[i] >> c[i];
	calc(e[0], a, 5);
	calc(e[1], b, 3);
	calc(e[2], c, 2);
	
	rep(i, 4) rep(j, m + 1) dp[i][j] = -INF;
	dp[0][0] = 0;
	rep(i, 3) rep(j, m + 1) if(dp[i][j] > -INF){
		rep(k, m - j + 1) dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + e[i][k]);
	}
	printf("%.9f\n", dp[3][m]);
	
	return 0;
}