思路
神仙概率dp
由于期望的线性性质，能够想到最后要求的期望价值就是把每个卡牌发动的概率(g_i)乘上伤害(val_i)之后加到一起
然后怎么求(g_i)呢，肯定是要dp的
我想了例如dp[i][j]表示第i张纸牌还有j次的考虑机会，dp[i][j]表示第i轮牌j发动的概率，但是都没有想出转移
发现每个牌一局游戏只能够发动一次，而且前面发动一次之后后面的纸牌不能再发动
然后发现第0张纸牌发动的概率是(p[0]=(1-(1-k[0])^r))（总概率-每一回合都不放的概率为有1回合放的概率）
第一张纸牌发动会受到第0张纸牌的影响，如果第0张纸牌不发动，第一张发动的概率就是(p[1]=(1-(1-k[1])^r))，如果第0张发动，则概率为(p[1]=(1-(1-k[1])^{r-1}))，每一张牌发动的概率只依赖于前面，且只依赖于有几张纸牌发动，所以可以把有几张纸牌发动压进状态里，然后就可以dp了
设dp[i][j]表示前i张纸牌，有j张发动的概率
决策自然是有两种：第i张发动/第i张不发动
如果第i张发动，则前面i-1张中有j-1张发动，第i张发动的概率为(p[i]=(1-(1-k[i])^{r-j+1}))
如果第i张不发动，则前面i-1张中有j张发动，第i张不发动的概率为(p[i]=(1-k[i])^{r-j})
然后就得出状态转移方程为(dp[i][j]=dp[i-1][j-1]*(1-(1-k[i])^{r-j+1})+dp[i-1][j]*(1-k[i])^{r-j})
所以(g_i=sum_{j=0}^{min(i-1,r)}dp[i-1][j]*(1-(1-k[i])^{r-j}))
然后没了
注意多组数据，数组要清空
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int T,n,m,val[230];
double k[230],dp[230][140],g[230];
double pow(double a,int b){
double ans=1;
while(b){
if(b&1)
ans=(ans*a);
a=(a*a);
b>>=1;
}
return ans;
}
int main(){
// freopen("2.in","r",stdin);
// freopen("test.out","w",stdout);
scanf("%d",&T);
while(T--){
double ans=0;
memset(val,0,sizeof(val));
memset(k,0,sizeof(k));
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lf %d",&k[i],&val[i]);
}
// printf("ok
");
dp[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=min(i,m);j++){
if(j>0){
dp[i][j]+=dp[i-1][j-1]*(1-pow((1-k[i]),m-j+1));
}
dp[i][j]+=dp[i-1][j]*(pow(1-k[i],m-j));
}
// printf("ok
");
for(int i=1;i<=n;i++)
for(int j=0;j<=min(i-1,m);j++)
g[i]+=dp[i-1][j]*(1-pow(1-k[i],m-j));
for(int i=1;i<=n;i++)
ans=ans+g[i]*val[i];
printf("%.10lf
",ans);
}
return 0;
}