样例输入1
3 1 0
10 20 30
-1 -1 2
样例输入2
5 1 2
36 44 13 83 63
-1 2 -1 2 1
样例输出1
0.300000
样例输出2
0.980387
【思路】
DP+概率
设f[i][j][k]表示共i场比赛赢j场且当前背包容量为k时的概率，则有：
f[i+1][j][k] += f[i][j][k]*(1-p[i+1])
f[i+1][j+1][k+a[i+1]] += f[i][j][k]*p[i+1]
其中n小而k大所以只用计算到n即可。提前按a值将数据sort一遍以免出现负值。
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define FOR(a,b,c) for(int a=(b);a<=(c);a++) 5 using namespace std; 6 7 const int N = 200+10; 8 struct node { 9 int a; double p; 10 bool operator <(const node& rhs) const { 11 return a>rhs.a; 12 } 13 }ns[N]; 14 15 double f[N][N][N]; 16 int n,K,L; 17 18 int main() { 19 scanf("%d%d%d",&n,&L,&K); 20 FOR(i,1,n) { 21 scanf("%lf",&ns[i].p); 22 ns[i].p/=100; 23 } 24 FOR(i,1,n) scanf("%d",&ns[i].a); 25 sort(ns+1,ns+n+1); 26 f[0][0][min(K,n)]=1; 27 FOR(i,0,n-1) FOR(j,0,i) FOR(k,0,n) 28 { 29 f[i+1][j][k] += f[i][j][k]*(1-ns[i+1].p); 30 int t=k+ns[i+1].a; 31 t=min(t,n); 32 if(t<0) continue; 33 f[i+1][j+1][t] += f[i][j][k]*ns[i+1].p; 34 } 35 double ans=0; 36 FOR(j,L,n) FOR(k,0,n) 37 ans += f[n][j][k]; 38 printf("%.6lf",ans); 39 return 0; 40 }
再次感受到tyvj满满的恶意(╯°Д°)╯︵ ┻━┻
tyvj P1864 [Poetize I]守卫者的挑战（DP+概率）
原文：http://www.cnblogs.com/lidaxin/p/5166257.html