题意：给定n个对手，至少要击败其中 l 个人，现在有口袋容量为 k下面n个数字表示击败这个人的概率
下面n个数字（若为-1表示击败这个人可以获得一个金币，若>0则表示可以增加口袋容量为这个数字）
求：至少击败其中的l个人，且获得的总口袋容量 >= 获得的金币个数 的概率是多少。（即任何时候金币都不能放不下）
思路：设dp[i][j][k]表示当前前i个人已经战胜j个人，且剩余口袋容量为k的概率，简单的推下公式即可。有一点需要主要，可能一开始
剩余口袋容量<0后来大于0，所以要加一个常数不让它为负，只要最后剩余容量>=0即可。详见代码：
/*********************************************************
file name: codeforces167B.cpp
author : kereo
create time: 2015年02月01日 星期日 21时34分15秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=200+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,m,k;
int a[N];
double p[N],dp[N][N][2*N+10];
int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
memset(dp,0,sizeof(dp));
dp[0][0][N+k]=1.0;
for(int i=1;i<=n;i++){
scanf("%lf",&p[i]);
p[i]/=100;
}
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
for(int k=0;k<=2*N;k++){
if(a[i] == -1){
if(k)
dp[i][j+1][k-1]+=dp[i-1][j][k]*p[i];
}
else
dp[i][j+1][min(2*N,k+a[i])]+=dp[i-1][j][k]*p[i];
dp[i][j][k]+=dp[i-1][j][k]*(1-p[i]);
}
}
}
double ans=0;
for(int i=m;i<=n;i++)
for(int j=N;j<=2*N;j++)
ans+=dp[n][i][j];
printf("%f\n",ans);
}
return 0;
}codeforces 167B Wizards and Huge Prize 概率dp
原文：http://blog.csdn.net/u011645923/article/details/43376601