Codeforces Beta Round #28 (Codeforces format)

题目链接： http://codeforces.com/contest/28/problem/C

题意：

有 $n$ 个人，$m$ 间浴室，每间浴室有$a[ i ]$个浴缸，每个人要洗澡的话都要排队，假如一群人进入同一个浴室，他们总倾向于使得最长的队伍最短，现在问你所有队伍中最长的期望？

中文题解：

用状态 $dp[i][j][k]$ 表示还剩 $i$ 间浴室，还剩 $j$ 个人，之前最长队伍的长度为 $k$ 的期望最长队伍长度。

那么状态转移方程为:

**$dp[i][j][k] = \sum_{i=1}^{{m}\sum_{j=0}}{n}\sum_{k=1}^{{n}\sum_{c=1}}{j}(dp[i-1][j-c][max(k, \frac{c+a[i]-1}{a[i]})] * \frac{(i-1)^{j-c}}{ i^j } * C(j, c)) $**

其中 $c$ 是枚举当前去第 $j$ 间浴室的人数。

那么答案就是 $dp[m][n][0]$ 。

时间复杂度：$O(n^{3}*m)$

英文题解：

This problem is solved by dynamic programming

Consider the following dynamics: $dp[i][j][k]$.

$i$ --- number of not yet processed students,

$j$ --- number of not yet processed rooms,

$k$ --- maximum queue in the previous rooms.

The value we need is in state $dp[n][m][0]$. Let's consider some state $(i, j, k)$ and search through all $c$ from 0 to $i$. If $c$ students will go to $j$th room, than a probability of such event consists of factors: $C_{i}^{c}$ --- which students will go to $j$th room.

$(1 / j)^c· ((j - 1) / j)^{i-c}$ --- probability, that $c$ students will go to $j$th room,and the rest of them will go to the rooms from first to $j - 1$th.

Sum for all $ñ$ from 0 to $i$ values of

$(1 / j)^c· ((j - 1) / j)^{i-c}·C_{i}^{c}· dp[i-c][j-1][mx]$ . Do not forget to update maximum queue value and get the accepted.

代码：

#include<bits/stdc++.h>

#pragma GCC optimize ("O3")

using namespace std;

typedef long long ll;

const int mod = 1e9+7;

int n,m;

int a[56];

double dp[56][56][56];

double C[56][56];

//题解：

//http://www.cnblogs.com/LzyRapx/p/7692702.html

int main()

{

	cin>>n>>m;

	C[0][0] = 1.0;

	for(int i=1;i<=55;i++)

	{

		C[i][0] = 1.0;

		for(int j=1;j<=i;j++)

		{

			C[i][j] = C[i-1][j-1] + C[i-1][j];

		}

	}

	for(int i=1;i<=m;i++) cin>>a[i];

	for(int i=0;i<=n;i++) dp[0][0][i] = i;

	for(int i=1;i<=m;i++)

	{

		for(int j=0;j<=n;j++)

		{

			for(int k=0;k<=n;k++)

			{

				for(int c=0;c<=j;c++)

				{

					int Max = max(k,(c+a[i]-1)/a[i]);

					dp[i][j][k] += dp[i-1][j-c][Max] * pow(i-1,j-c) / pow(i,j) * C[j][c];

				}

			}

		}

	}

	printf("%.10f\n",dp[m][n][0]);

	return 0;

}

巴特西

Codeforces #28 C.Bath Queue (概率dp)

Codeforces Beta Round #28 (Codeforces format)

题目链接： http://codeforces.com/contest/28/problem/C

题意：

有 \(n\) 个人，\(m\) 间浴室，每间浴室有\(a[ i ]\)个浴缸，每个人要洗澡的话都要排队，假如一群人进入同一个浴室，他们总倾向于使得最长的队伍最短，现在问你所有队伍中最长的期望？

中文题解：

用状态 \(dp[i][j][k]\) 表示还剩 \(i\) 间浴室，还剩 \(j\) 个人，之前最长队伍的长度为 \(k\) 的期望最长队伍长度。

那么状态转移方程为:

**$dp[i][j][k] = \sum_{i=1}^{{m}\sum_{j=0}}{n}\sum_{k=1}^{{n}\sum_{c=1}}{j}(dp[i-1][j-c][max(k, \frac{c+a[i]-1}{a[i]})] * \frac{(i-1)^{j-c}}{ i^j } * C(j, c)) $**

其中 \(c\) 是枚举当前去第 \(j\) 间浴室的人数。

那么答案就是 \(dp[m][n][0]\) 。

时间复杂度：\(O(n^{3}*m)\)

英文题解：

This problem is solved by dynamic programming

Consider the following dynamics: \(dp[i][j][k]\).

\(i\) --- number of not yet processed students,

\(j\) --- number of not yet processed rooms,

\(k\) --- maximum queue in the previous rooms.

The value we need is in state \(dp[n][m][0]\). Let's consider some state \((i, j, k)\) and search through all \(c\) from 0 to \(i\). If \(c\) students will go to \(j\)th room, than a probability of such event consists of factors: \(C_{i}^{c}\) --- which students will go to \(j\)th room.

\((1 / j)^c· ((j - 1) / j)^{i-c}\) --- probability, that \(c\) students will go to \(j\)th room,and the rest of them will go to the rooms from first to \(j - 1\)th.

Sum for all \(ñ\) from 0 to \(i\) values of

\((1 / j)^c· ((j - 1) / j)^{i-c}·C_{i}^{c}· dp[i-c][j-1][mx]\) . Do not forget to update maximum queue value and get the accepted.

代码：

最新文章

热门文章

巴特西

Codeforces #28 C.Bath Queue (概率dp)

Codeforces Beta Round #28 (Codeforces format)

题目链接： http://codeforces.com/contest/28/problem/C

题意：

有 \(n\) 个人，\(m\) 间浴室，每间浴室有\(a[ i ]\)个浴缸，每个人要洗澡的话都要排队，假如一群人进入同一个浴室，他们总倾向于使得最长的队伍最短，现在问你所有队伍中最长的期望？

中文题解：

用状态 \(dp[i][j][k]\) 表示还剩 \(i\) 间浴室，还剩 \(j\) 个人，之前最长队伍的长度为 \(k\) 的期望最长队伍长度。

那么状态转移方程为:

$dp[i][j][k] = \sum_{i=1}{m}\sum_{j=0}{n}\sum_{k=1}{n}\sum_{c=1}{j}(dp[i-1][j-c][max(k, \frac{c+a[i]-1}{a[i]})] * \frac{(i-1)^{j-c}}{ i^j } * C(j, c)) $

其中 \(c\) 是枚举当前去第 \(j\) 间浴室的人数。

那么答案就是 \(dp[m][n][0]\) 。

时间复杂度：\(O(n^{3}*m)\)

英文题解：

This problem is solved by dynamic programming

Consider the following dynamics: \(dp[i][j][k]\).

\(i\) --- number of not yet processed students,

\(j\) --- number of not yet processed rooms,

\(k\) --- maximum queue in the previous rooms.

The value we need is in state \(dp[n][m][0]\). Let's consider some state \((i, j, k)\) and search through all \(c\) from 0 to \(i\). If \(c\) students will go to \(j\)th room, than a probability of such event consists of factors: \(C_{i}^{c}\) --- which students will go to \(j\)th room.

\((1 / j)^c· ((j - 1) / j)^{i-c}\) --- probability, that \(c\) students will go to \(j\)th room,and the rest of them will go to the rooms from first to \(j - 1\)th.

Sum for all \(ñ\) from 0 to \(i\) values of

\((1 / j)^c· ((j - 1) / j)^{i-c}·C_{i}^{c}· dp[i-c][j-1][mx]\) . Do not forget to update maximum queue value and get the accepted.

代码：

最新文章

热门文章

**$dp[i][j][k] = \sum_{i=1}^{{m}\sum_{j=0}}{n}\sum_{k=1}^{{n}\sum_{c=1}}{j}(dp[i-1][j-c][max(k, \frac{c+a[i]-1}{a[i]})] * \frac{(i-1)^{j-c}}{ i^j } * C(j, c)) $**