传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4089
本来可以一遍过的，结果mle了一发。。。注意要用滚动数组。
令f(i, j)表示队列剩余i个人，这个人排第j时遇到那种情况的概率，则有
f(i, j) = p1 * f(i, j) + p2 * f(i, (j - 2) % i + 1) + p3 * f(i - 1, j - 1) + p4 * (j <= k).
注意最后哪里有一个强制转换，若j <= k则p4 * 1，若j > k则p4 * 0.把方程移项，得
f(i, j) = ( p2 * f(i, (j - 2) % i + 1) + p3 * f(i - 1, j - 1) + p4 * (j <= k) ) / (1 - p1).
这里最大的问题就是f(i, (j - 2) % i + 1)，因为这个值在这之前不是已知的，不好转移。此时，把这个方程抽象出来，就变成了一个简单的一次方程，形如：
x[n] = p * x[n - 1] + a[n]
x[n - 1] = p * x[n - 2] + a[n - 1]
...
x[1] = p * x[n] + a[1].
这个一次方程自己在纸上写一写就知道如何解了，同理，可以通过这种方式求出所有的f值了。
#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn = 2010;
const double eps = 1e-8;
int n, m, k;
double p1, p2, p3, p4, f[2][maxn], p, poww[maxn] = {1.0}, a;
int main(void) {
//freopen("in.txt", "r", stdin);
while (scanf("%d%d%d%lf%lf%lf%lf", &n, &m, &k, &p1, &p2, &p3, &p4) != EOF) {
if (fabs(p1 + p2 - 1) < eps) {
puts("0.00000");
continue;
}
p = p2 / (1.0 - p1);
for (int i = 1; i <= n + 2; ++i) {
poww[i] = poww[i - 1] * p;
}
memset(f, 0, sizeof f);
f[1][1] = p4 / (1 - p1 - p2);
for (int i = 2; i <= n; ++i) {
f[i & 1][1] = p4 / (1.0 - p1);
for (int j = 2; j <= i; ++j) {
a = (p3 * f[i & 1 ^ 1][j - 1] + p4 * (double)(j <= k)) / (1.0 - p1);
f[i & 1][1] += a * poww[i + 1 - j];
}
f[i & 1][1] /= (1.0 - poww[i]);
for (int j = 2; j <= i; ++j) {
f[i & 1][j] = (p2 * f[i & 1][j - 1] + p3 * f[i & 1 ^ 1][j - 1] + p4 * (double)(j <= k)) / (1.0 - p1);
}
}
printf("%.5f
", f[n & 1][m]);
}
return 0;
}