[报告]codeforces 175d Plane of Tanks: Duel

报告]codeforces 175d Plane of Tanks: Duel"/>

[报告]codeforces 175d Plane of Tanks: Duel

Abstract

codeforces 175d Plane of Tanks: Duel

dp 概率 乱搞

Source

Description

战车少女互殴

两辆战车对战，战车有如下属性：hp，射击时间间隔，击中目标概率，伤害值范围（判定击中目标后等概率选一个范围内的值作为给目标的伤害）。hp降为0战车就不能打了。所以这是一个dnd世界

求第二辆车被摧毁的概率。

Solution

我见过的最没节操的概率题……

一开始设计的状态为f(hp0, hp1, t)表示已知当前第一辆车hp为hp0，第二辆车为hp1，时刻为t的时候第二辆车被摧毁的概率。有效的t实际上最大只有lcm(t[0], t[1])，里面还有很多是没用的可以离散化掉。但这样做的markov链是有环的，需要高斯消元。但是状态数实在太多高斯消元肯定超时……

然后就yy了很久，实在想不出来了，去看题解……

题解表示：对于两边根本打不中（击中目标概率为0）的情况特判。否则记f[i][j]表示当前战车i还剩j的hp的概率，模拟整个过程，直到某一边还存活的概率<EPS……

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const double EPS = 1e-7;int hp[2], dt[2], l[2], r[2], pi[2];
double p[2], a[2];
double f[2][222];
int t[2];void update(int i) {int j, k;f[i][0] = 0;for (j = 1; j <= hp[i]; ++j) {double h = f[i][j]*(1-p[!i])/(r[!i]-l[!i]+1);f[i][j] *= p[!i];for (k = l[!i]; k <= r[!i]; ++k)f[i][max(0, j-k)] += h;}for (a[i]=0, j=1; j <= hp[i]; ++j)a[i] += f[i][j];
}int main() {int i, j, k, d;for (i = 0; i < 2; ++i) {cin>>hp[i]>>dt[i]>>l[i]>>r[i]>>pi[i];p[i] = pi[i]/100.0;}if (pi[0]==100) return puts("0"), 0;else if (pi[1]==100) return puts("1"), 0;a[0] = a[1] = f[0][hp[0]] = f[1][hp[1]] = 1;double ans = 0;for (; a[0]>EPS && a[1]>EPS; ) {i = t[0]<=t[1]?0:1;t[i] += dt[i];update(!i);if (i==0) ans += a[0]*f[1][0];}printf("%.6f\n", ans);return 0;
}

转载于:.html