题解 P3239 【[HNOI2015]亚瑟王】

[也许更好的阅读体验](https://www.cnblogs.com/Morning-Glory/p/11225947.html) # $\mathcal{Description}$ 给出$n$个技能，每个技能按输入顺序有$p[i]$的概率释放并造成$d[i]$的伤害。每轮游戏从前往后顺序查看每个技能，若技能发动过则跳过，没发动过则以$p[i]$的技能发动，即每个技能只能发动一次，若将一个技能发动，则进行下一轮游戏，没有成功发动或被跳过就查看下一个技能，一轮游戏可能每个技能都不发动，问$r$轮游戏一共能造成的伤害期望。 输入方式 T组数据 接下来组数据 每组数据第一行$n,r$ 接下来$n$行$p_i,d_i$表示该技能发动概率以及伤害 1 <= T <= 444， 1 <= n <= 220， 0 <= r <= 132， 0 < p_i < 1， 0 <= d_i <= 1000 输出格式 每组数据输出一行期望伤害，建议保留$10$位小数 # $\mathcal{Solution}$ 因为有一个顺序查看的限制，没有后效性的状态是十分不好设的，因为不知道前面有几个技能发动了，若一个技能前面的技能在某轮发动了，则该技能本轮一定不能发动，若前面有些技能发动过，则它们都会被跳过 为了解决这种情况，我们设状态时试着强制限制技能发动（$nr$枚举情况），当然，设的状态仍然要满足 __所有__ 情况都考虑在内 设$f[i][j]$表示对前$i$个技能进行了$j$轮游戏造成的 __概率__ 若有前$i$个技能进行了$j$ 则有$j$轮不会考虑第$i+1$个技能 即有$r-j$轮游戏选择了$i$之后的技能 此时考虑第$i+1$个技能的情况，分为两种 1. 有$p[i+1]^{r-j}$的概率$i+1$号技能从未发动 2. 有$1-p[i+1]^{r-j}$的概率$i+1$号技能发动过 需要注意的是，此时 __已经__ 确定前$i$个技能进行并 __只进行__ 了$j$轮游戏，其概率应该也计算在内 所以有 1. $f[i+1][j]+=1-p[i+1]^{r-j}f[i][j]$ 2. $f[i+1][j+1]+=(1-p[i+1]^{r-j})f[i][j]$ $j+1$要小于等于$r$ 初值$f[0][0]=1$，答案在中途计算 计算了概率，别忘了求的是期望伤害，在求概率的时候顺便用概率乘以伤害 # $\mathcal{Code}$ ```cpp /******************************* Author:Morning_Glory LANG:C++ Created Time:2019年07月22日 星期一 14时17分22秒 *******************************/ #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 255; int T,n,r; double ans; double p[maxn],d[maxn]; double f[maxn][maxn]; int main() { scanf("%d",&T); while (T--){ scanf("%d%d",&n,&r); for (int i=1;i<=n;++i) scanf("%lf%lf",&p[i],&d[i]); for (int i=0;i<=n;++i) for (int j=0;j<=r;++j) f[i][j]=0; ans=0,f[0][0]=1; for (int i=0;i<=n-1;++i){ int k=min(i,r); for (int j=0;j<=k;++j){ double tmp=pow(1-p[i+1],r-j); f[i+1][j]+=f[i][j]*tmp; if (j+1<=r){ f[i+1][j+1]+=f[i][j]*(1-tmp); ans+=f[i][j]*(1-tmp)*d[i+1];//计算第i+1张牌造成的期望伤害 } } } printf("%.10lf\n",ans); } return 0; } ``` 本篇博客亦被收进[期望总结](https://blog.csdn.net/Morning_Glory_JR/article/details/96731105)