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;
}