1062 ModricWang的撒币游戏

思路

此题为2017年ACM-ICPC亚洲区域赛乌鲁木齐赛区的A题，现场94个队中有38个队做出此题。在这里作为满分以外的题，是为了让大家看一下外面一些题的风格，不要被三位助教的出题风格所局限。

此题首先需要知道一些高中数学概率论的知识。扔起N个硬币，如果每个硬币下落时，正反面朝上的概率都是确定的，那么这些硬币中正面朝上的数量是呈二项分布的。

考虑使用DP，\(prob[i][j]\) 表示扔了第i次后，有j个硬币正面朝上的概率。首先根据题设，\(prob[0][0]=1\)，每次根据\(i\)这一行来推出\(i+1\)这一行，扔硬币的过程会让\(prob[i][j]\) 以二项分布分散到\(prob[i+1][p]和prob[i+1][p+k]\) 这\(k+1\) 项里。j、p和n的关系如下：\(p \leq j \leq p+k \leq n\) ，意义为：j表示当前有多少个硬币向上，p表示下一步最少有多少个硬币向上，(p+k)表示下一步最多有多少个硬币向上。所谓的最优策略就是，让p尽量的大，也就是扔硬币的时候尽量选朝下的扔。最终答案就是 \(\Sigma_{i=1}^{n} i*prob[m][i]\)。

具体进行操作时可以有一些优化策略，例如

使用滚动数组来节省空间
忽略概率小于\(1e-3\) 的项

但是我做的时候没有采取这些策略，因为

根据计算，内存空间是足够的
虽然\(O(Tnmk)\) 在此题中达到了\(1e9\)的数量级，但是计算过程中的核心语句是\(a+=b*c\) 的形式，这样的语句在X86架构下就是一条FMA指令的事，不必担心常数的问题。 reference: 乘积累加运算 - 维基百科

and FMA指令集 - 维基百科

时间复杂度:\(O(Tnmk)\)，空间复杂度\(O(nm)\)

代码：



#include <iostream>

#include <iomanip>

#include <cstring>

using std::ios_base;

using std::cin;

using std::cout;

using std::min;

using std::fixed;

using std::setprecision;

const int MaxNum = 100 + 7;

double prob[MaxNum][MaxNum];

double binomial_distribution[MaxNum][MaxNum];

//计算二项分布的概率值

void get_binomial_distribution() {

	double prob_sum = 1;

	for (int i = 1; i < MaxNum; i++) {

		double C = 1;

		prob_sum *= 2;

		binomial_distribution[i][0] = C/prob_sum;

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

			C = C*(i - j + 1)/j;

			binomial_distribution[i][j] = C/prob_sum;

		}

	}

}

int main() {

#ifdef ONLINE_JUDGE

	ios_base::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

#else

	freopen("in.txt", "r", stdin);

	freopen("out.txt", "w", stdout);

#endif

	get_binomial_distribution();

	int T;

	while (cin >> T) {

		while (T--) {

			int n, m, k;

			cin >> n >> m >> k;

			memset(prob, 0, sizeof(prob));

			prob[0][0] = 1;

			for (int step = 1; step <= m; step++) {

				for (int i = 0; i <= n; i++) {

					int begin_pos = min(i, n - k);	//这就是思路里写的p

					for (int j = 0; j <= k; j++) {

						prob[step][begin_pos + j] += prob[step - 1][i]*binomial_distribution[k][j]; //DP过程

					}

				}

			}

			double ans = 0;

			for (int i = 1; i <= n; i++) {

				ans += i*prob[m][i];

			}

			cout << fixed << setprecision(3) << ans << "\n";

		}

	}

}

Prob

2016级算法第五次上机-G.ModricWang的撒币游戏

1062 ModricWang的撒币游戏

思路

代码：