题目:
洛谷 3239 https://www.luogu.org/problemnew/show/P3239
分析:
卡牌造成的伤害是互相独立的, 所以 \(ans=\sum f_i\cdot d_i\) , 其中 \(f_i\) 表示第 \(i\) 张牌 在整局游戏中 发动技能的概率. 那么现在的问题是求 \(f_i\) .
考虑对于一张特定的牌 \(i\) , 它发动技能的概率显然和比它大的牌是否发动技能无关. 并且, 这个概率只和有 多少个 比它小的牌发动了技能有关, 而与具体是哪几张和发动顺序都无关. 为什么呢? 考虑正难则反, 它发动技能的概率是 1 减去在 \(r\) 轮游戏中都没有发动技能的概率. 但并不是 \(1-(1-p_i)^r\) , 因为如果有 \(j\) 张比 \(i\) 小的牌发动了技能, 那么这 \(j\) 轮中牌 \(i\) 不会发动技能的概率是 \(1\) 而不是 \(1-p_i\) , 因为这一轮已经在前面某张牌发动技能时结束了. 所以答案应为 \(1-(1-p_i)^{r-j}\) .
用 \(dp_{i,j}\) 表示前 \(i\) 张牌中发动了 \(j\) 张的概率, 那么有转移 (分别对应第 \(i\) 张是否发动技能):
\[dp_{i,j}=dp_{i-1,j}\cdot (1-p_i)^{r-j}+dp_{i-1,j-1}\cdot \left(1-(1-p_i)^{r-(j-1)}\right)\]
那么就有
\[f_i=\sum_{j=0}^{i-1} dp_{i-1,j}\cdot \left(1-(1-p_i)^{r-j}\right)\]
代码:
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <cctype>
- #include <cmath>
- using namespace std;
- namespace zyt
- {
- template<typename T>
- inline bool read(T &x)
- {
- char c;
- bool f = false;
- x = 0;
- do
- c = getchar();
- while (c != EOF && c != '-' && !isdigit(c));
- if (c == EOF)
- return false;
- if (c == '-')
- f = true, c = getchar();
- do
- x = x * 10 + c - '0', c = getchar();
- while (isdigit(c));
- if (f)
- x = -x;
- return true;
- }
- inline bool read(double &x)
- {
- return ~scanf("%lf", &x);
- }
- template<typename T>
- inline void write(T x)
- {
- static char buf[20];
- char *pos = buf;
- if (x <0)
- putchar('-'), x = -x;
- do
- *pos++ = x % 10 + '0';
- while (x /= 10);
- while (pos> buf)
- putchar(*--pos);
- }
- inline void write(const double &x, const int fixed = 9)
- {
- printf("%.*f", fixed, x);
- }
- const int N = 230, R = 150;
- double p[N], dp[N][R];
- int n, r, d[N];
- int work()
- {
- int T;
- read(T);
- while (T--)
- {
- read(n), read(r);
- for (int i = 1; i <= n; i++)
- read(p[i]), read(d[i]), memset(dp[i], 0, sizeof(int[min(r, i) + 1]));
- dp[0][0] = 1;
- for (int i = 1; i <= n; i++)
- for (int j = 0; j <= min(r, i); j++)
- dp[i][j] = (j ? dp[i - 1][j - 1] * (1 - pow(1 - p[i], r - j + 1)) : 0)
- + dp[i - 1][j] * pow(1 - p[i], r - j);
- double ans = 0;
- for (int i = 1; i <= n; i++)
- {
- double pp = 0;
- for (int j = 0; j < min(r, i); j++)
- pp += dp[i - 1][j] * (1 - pow(1 - p[i], r - j));
- ans += pp * d[i];
- }
- write(ans, 10), putchar('\n');
- }
- return 0;
- }
- }
- int main()
- {
- return zyt::work();
- }
来源: http://www.bubuko.com/infodetail-3059527.html