http://poj.org/problem?id=2151
题意：T个队伍M条题目，给出每个队伍i的每题能ac的概率p[i][j]，求所有队伍至少A掉1题且冠军至少A掉N题的概率（T<=1000, M<=30）
#include <cstdio>
#include <cstring>
using namespace std;
const int T=1005, M=35;
double d[T][M], p[T][M];
int n, m, N;
void clr() {
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) d[i][j]=0;
}
int main() {
while(scanf("%d%d%d", &m, &n, &N), !(m==0&&n==0&&N==0)) {
for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) scanf("%lf", &p[i][j]);
for(int i=1; i<=n; ++i) d[i][0]=1;
for(int i=1; i<=n; ++i)
for(int k=1; k<=m; d[i][0]*=1-p[i][k], ++k)
for(int j=m; j; --j) d[i][j]=d[i][j]*(1-p[i][k])+d[i][j-1]*p[i][k];
//for(int i=1; i<=n; ++i) { for(int j=0; j<=m; ++j) printf("%.2f ", d[i][j]); puts(""); }
for(int i=1; i<=n; ++i) for(int j=m; j; --j) d[i][j]+=d[i][j+1];
double ans=0, sum;
for(int i=1; i<=n; ++i) {
sum=d[i][N];
for(int j=1; j<i; ++j) sum*=(d[j][1]-d[j][N]);
for(int j=i+1; j<=n; ++j) sum*=d[j][1];
ans+=sum;
}
printf("%.3f\n", ans);
clr();
}
return 0;
}
我们只需要设状态就行了= =随便搞...
设f[i][j][k]表示第i队解决j~k个问题的概率
$$ans=\sum_{i} \left( f[i][N][M] * \prod_{j<i} f[j][1][N-1] * \prod_{j>i} f[j][1][M] \right) $$
这样就能不重不漏....（不难理解，我觉得这个很简单的吧= =
然后我们来一发前缀和，d[i][j]表示第i队解决至少j个问题的概率
$$ans=\sum_{i} \left( d[i][N] * \prod_{j<i} ( d[j][1]-d[j][N] ) * \prod_{j>i} d[j][1] \right) $$
问题转化为如何求d[i][j]...
设d'[i][j]表示第i队解决j个问题的概率
我们类似背包依次加入每个问题，有
d[i][j]=d[i][j]*(1-p[i][k])+d[i][j-1]*p[i][k]（自己好好思考= =，我拐了好多个弯才想出来QAQ
于是就ok了。。。