【codeforces 175D】 Plane of Tanks: Duel

时间:2022-06-16 14:30:45

http://codeforces.com/problemset/problem/175/D (题目链接)

题意

  A,B两人玩坦克大战,坦克有生命值,射击间隔,伤害范围,未命中的概率。问A赢的概率是多少。

Solution

  直接做并不好做,注意到精度要求只有$10^{-4}$,也就是说当射击次数达到一定上限之后,满足了精度要求我们就可以不做了。我们考虑按照时间dp。怎么设计状态呢,如果$f[i][j]$表示A还剩$i$点生命值,B还剩$j$点生命值,这样复杂度太高了,我们考虑将A和B剩余生命分开dp。

  $f[i][j]$表示A被射击$i$次后,还剩下$j$点生命值的概率,特殊的,$f[i][0]$表示在射击次数$<=i$时A死亡的概率。B的同理。转移很显然:$$f[i][max(0,j-x)]=f[i-1][j]*(1-p)/(r-l+1)+f[i-1][j]*p$$

  我们预处理出$D$次射击后A,B的dp数组。考虑怎么计算答案。如果B在第$K$轮挂掉了,那么要求A在第$K$轮射击之前没有死,那么这个时候A被射击了多少次呢,我们可以算出来:$$T=((K-1)*dt_A+dt_B-1)/dt_B$$

  那么A在第$K$轮胜出的概率为:$$ans_K=(1-f_A[T][0])*f_B[K][0]$$

  最后把所有的$ans$累加起来就可以了。

细节

  mdzz写了半天,各种坑点,本机1s多CF上居然TLE了是什么鬼嘛,智力-2。

  时间设到4000差不多够了。

  当$f[i][j]==0$的时候不dp,但是!但是!!要这样写:$f[i][j]<=eps$。。一把辛酸泪啊T_T

  要特判$p_A=100$和$p_B=100$的情况,而且前者一定要写在后者之前T_T。

代码

// codeforces175D
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define eps 1e-8
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; double f[2][4010][210],p[2],ans;
int hp[2],dt[2],L[2],R[2],P[2],n,x; int main() {
for (int i=0;i<2;i++) scanf("%d%d%d%d%d",&hp[i],&dt[i],&L[i],&R[i],&P[i]);
if (P[0]==100) {puts("0");return 0;} //must first
if (P[1]==100) {puts("1");return 0;}
f[0][0][hp[0]]=f[1][0][hp[1]]=1;p[0]=P[0]/100.0;p[1]=P[1]/100.0;
for (x=1;x<=4000;x++) {
for (int i=0;i<2;i++)
for (int l=i^1,j=1;j<=hp[i];j++) {
if (f[i][x-1][j]<=eps) continue;
for (int k=L[l];k<=R[l];k++)
f[i][x][max(0,j-k)]+=f[i][x-1][j]*(1-p[l])/(R[l]-L[l]+1);
f[i][x][j]+=f[i][x-1][j]*p[l];
}
f[0][x][0]+=f[0][x-1][0];
}
for (int i=1;i<=x;i++) {
int T=((i-1)*dt[0]+dt[1]-1)/dt[1];
if (T>x) break;
ans+=(1-f[0][T][0])*f[1][i][0];
}
printf("%.6lf\n",ans);
return 0;
}