[HNOI2015]亚瑟王[期望DP]

也许更好的阅读体验
$Description$Description
给出 $n$n个技能，每个技能按输入顺序有 $p\left[i\right]$p[i]的概率释放并造成 $d\left[i\right]$d[i]的伤害。每轮游戏从前往后顺序查看每个技能，若技能发动过则跳过，没发动过则以 $p\left[i\right]$p[i]的技能发动，即每个技能只能发动一次，若将一个技能发动，则进行下一轮游戏，没有成功发动或被跳过就查看下一个技能，一轮游戏可能每个技能都不发动，问 $r$r轮游戏一共能造成的伤害期望。

输入方式
T组数据
接下来组数据
每组数据第一行 $n,r$n,r
接下来 $n$n行 $p_i,d_i$pi​,di​表示该技能发动概率以及伤害

$1\&lt;=T\&lt;=444，1\&lt;=n\&lt;=220，0\&lt;=r\&lt;=132，0\&lt;p_i\&lt;1，0\&lt;=d_i\&lt;=1000$1<=T<=444，1<=n<=220，0<=r<=132，0<pi​<1，0<=di​<=1000

输出格式
每组数据输出一行期望伤害，建议保留 $10$10位小数
$Solution$Solution
因为有一个顺序查看的限制，没有后效性的状态是十分不好设的，因为不知道前面有几个技能发动了，若一个技能前面的技能在某轮发动了，则该技能本轮一定不能发动，若前面有些技能发动过，则它们都会被跳过
为了解决这种情况，我们设状态时试着强制限制技能发动（ $nr$nr枚举情况），当然，设的状态仍然要满足 所有 情况都考虑在内
设 $f\left[i\right]\left[j\right]$f[i][j]表示对前 $i$i个技能进行了 $j$j轮游戏造成的 概率
若有前 $i$i个技能进行了 $j$j
则有 $j$j轮不会考虑第 $i+1$i+1个技能
即有 $r-j$r−j轮游戏选择了 $i$i之后的技能
此时考虑第 $i+1$i+1个技能的情况，分为两种

1. 有 $p[i+1{]}^{r-j}$p[i+1]r−j的概率 $i+1$i+1号技能从未发动
2. 有 $1-p[i+1{]}^{r-j}$1−p[i+1]r−j的概率 $i+1$i+1号技能发动过

需要注意的是，此时 已经 确定前 $i$i个技能进行并 只进行 了 $j$j轮游戏，其概率应该也计算在内
所以有

1. $f[i+1]\left[j\right]+=1-p[i+1{]}^{r-j}f[i\left]\right[j]$f[i+1][j]+=1−p[i+1]r−jf[i][j]
2. $f[i+1][j+1]+=(1-p[i+1{]}^{r-j}\left)f\right[i\left]\right[j]$f[i+1][j+1]+=(1−p[i+1]r−j)f[i][j]

$j+1$j+1要小于等于 $r$r

初值 $f\left[0\right]\left[0\right]=1$f[0][0]=1，答案在中途计算

计算了概率，别忘了求的是期望伤害，在求概率的时候顺便用概率乘以伤害

$Code$Code

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

本篇博客亦被收进期望总结

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧