UVA11021 Tribles

Tribles - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题可以好好读读题，读输入那几个，我理解错题意还进行大量思考，可恶。。（我以为输入那几个是每种生物生或死的概率。非常低级的错误。）

题意：

开局给若干个生物，这个生物会在本回合发生以下行为后死掉：

p0 不生

p1 生1个

p2 生2个

p3 生3个

...

（这些概率p之和为1）

样例解释：

第一轮就得死光，0.33不生就死光了。

解法——dp:

我们设 f [ i ] 为开局一个生物，第 i 天内全部死光的期望。

我们求开局k个，m天，所以 ( f [m]  ) ^ k即可。

对于 f [ i ] 我们可以这样表示： （动态规划）（全概率公式（其实就是范围内所有情况的概率加起来））

f[ i ] = p0 + p1*f[ i-1] + p2*(f[ i-1] ^ 2) + ....

这个其实映射的是开局，

开局死，p0，期望加上

开局是p1 ，那下一轮只有一个，而这个需在 i - 1天内死掉，所以乘以期望f [ i - 1]

(一共 i 天嘛，已经过了1天了，剩下 i - 1天)

开局是p2 ， 那下一轮有两个，这两个都需在 i -1天内死掉，所以乘以 f[ i-1] * f[ i-1]

...

现在应该可以欣赏洛谷题解了。

代码：

关于初始化，可以看样例解释，第1天f[ 1 ]就是p0.

double ksm(double x, int y)
{
	if (x == 1) return 1;
	double res = 1, base = x;
	while (y) {
		if (y & 1) res = res * base;
		base = base * base;
		y >>= 1;
	}
	return res;
}

int n, k, m;
double arr[10005];
double sum[1005];

void solve(int ca)
{
	cin >> n >> k >> m;
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	double ans = 1;
	vector<double>f(m + 1);
	f[1] = arr[0];
	for (int i = 2; i <= m; i++)
	{
		f[i] = arr[0];
		for (int j = 1; j < n; j++)
		{
			f[i] += arr[j] * ksm(f[i - 1], j);
		}
	}
	printf("Case #%d: %.7lf\n", ca, ksm(f[m],k));
}
signed main()
{
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++)
	{
		solve(i);
	}
	return 0;
}