这题真心神题……
首先我们直接考虑第i轮选择谁，那么明显是做不了的，就变成了暴力
我们需要一些独特的DP技巧
首先，我们无视掉m轮的限制，把m次选择全部放在同一轮里面
设$DP[i][j]$为$[i,n]$中的人被选择$j$次的概率
那么显然$DP[0][m]=1$，因为根本没有0号，所以0一定不会被选择
那么转移就变成了
$DP[i][j]=DP[i-1][j]*(1-P[i-1])^j+DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$
解释:
首先$DP[i-1][j]*(1-P[i-1])^j$表示的是向前面递推到i-1人(因为这一次这一轮没有结束，当前卡牌没有被选择)，同样还是j次机会，上一张卡发动技能的概率是$P[i-1]$(因为上一张卡如果发动了技能就跳到下一轮了),那么不发动技能的概率就是$1-P[i-1]$，j轮不发动技能的概率就是$(1-P[i-1])^j$,前面的$DP[i-1][j]$意思是上一张卡没有发动技能结束回合，这次机会留到这张卡
$DP[i-1][j+1]*(1-(1-P[i-1])^{j+1})$意思是上一张卡在第j轮不幸被选中发动技能了，那么下一次想要选到当前卡牌必须跳到下一轮(所以是$j+1$)，后面的概率意思是上一张卡在前$j+1$轮发动技能的概率(因为直接选中这张卡后会判断当前这张卡有没有发动技能，前面是发动了技能的概率)，那么这次将会跳过这张卡来到当前卡
所以来到当前卡的期望就是上面两者的和
然而答案怎么统计呢?答案因为要统计伤害的期望，那么根据期望的线性性，我们知道第$i$张卡能来到j轮的期望为$DP[i][j]$(来到的意思就是没有在前面发动过技能)
所以$ans=DP[i][j]*(1-(1-P[i])^j)*D[i]$,其中$D[i]$表示的是伤害
怎么找一篇详细的题解那么难。。大部分题解也就两句话，迫使我这样的蒟蒻花很长时间去思考，那些神犇的思维能力太强一句话题解就会做了orzorz
UPD:hzwer的题解比我的好多了。。十分清晰易懂
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=255;
long double dp[N][N],P[N],D[N],ans;
int n,m,T;
long double Qpow(long double x,int y){
long double ans=1.0;
while(y){
if(y&1)ans=ans*x;
x*=x;
y>>=1;
}
return ans;
}
int main(){
freopen("4008.in","r",stdin);
freopen("4008.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++){
double x,y;
scanf("%lf %lf",&x,&y);
P[i]=x;D[i]=y;
}
dp[0][m]=1.0;
ans=0.0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j]*Qpow(1-P[i-1],j)+dp[i-1][j+1]*(1-Qpow(1-P[i-1],j+1));
ans+=dp[i][j]*(1-Qpow(1-P[i],j))*D[i];
}
}
printf("%.10lf\n",(double)ans);
}
return 0;
}
评论 (0)
