4832: [Lydsy2017年4月月赛]抵制克苏恩
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 673 Solved: 261
[Submit][Status][Discuss]
Description
Input
Output
对于每局游戏,输出一个数字表示总伤害的期望值,保留两位小数。
Sample Input
Sample Output
HINT
分析:
玩阴阳师的非洲人默默仰望炉石*。
因为期望dp都是逆推,一般还会套记搜。所以我就正着推了……(我期望dp弱啊)
定义状态f[t][i][j][k]表示克苏恩攻击第t次,还剩i只1滴血的奴隶主,j只2滴血的奴隶主,k只三滴血奴隶主的概率(注意是,概率)。
因为期望等于所有事件概率 * 数值 之和,
当克苏恩攻击人时 ans += f[t - 1][j][k][l] / (1 + j + k + l);
转移状态
f[t][j][k][l] += f[t - 1][j][k][l] / (1 + j + k + l);
if(j)f[t][j - 1][k][l] += f[t - 1][j][k][l] * j / (1 + j + k + l);
if(k)f[t][j + 1][k - 1][l + flag] += f[t - 1][j][k][l] * k / (1 + j + k + l);
if(l)f[t][j][k + 1][l - 1 + flag] += f[t - 1][j][k][l] * l / (1 + j + k + l);
你问我为啥没考虑30滴血被打完的情况?因为有草爹沉迷输出,见死不救啊。(咳咳)
好嘛,其实正确按题意应该会再加一维去考虑剩的血量问题,因为题上数据没考虑这个,就不用考虑了。
AC代码:
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
int T,K,A,B,C;
double f[][][][],ans;
int main(){
scanf("%d",&T);
scanf("\n%1c %1c",&a,&b)
while(T--){
; scanf("%d %d %d %d",&K,&A,&B,&C);
memset(f,,sizeof f);
f[][A][B][C] = ;
ans = ;
for(int t = ;t <= K;t++)
for(int j = ;j <= ;j++){
for(int k = ;k <= ;k++){
if(k + j > )break;
for(int l = ;l <= ;l++){
if(l + k + j > )break;
int flag = ((l + k + j) < ) ? : ;
f[t][j][k][l] += f[t - ][j][k][l] / ( + j + k + l);
ans += (f[t - ][j][k][l] / ( + j + k + l));
if(j)f[t][j - ][k][l] += f[t - ][j][k][l] * j / ( + j + k + l);
if(k)f[t][j + ][k - ][l + flag] += f[t - ][j][k][l] * k / ( + j + k + l);
if(l)f[t][j][k + ][l - + flag] += f[t - ][j][k][l] * l / ( + j + k + l);
}
}
}
printf("%.2lf",ans);
}
}