题目描述
输入格式
输出格式
数据范围与约定
对于 10% 的数据 N=1。
对于 30% 的数据 N=2。
对于全部数据 N≤4，M≤120 , A_i≤50。
样例输入1
1 21样例输出1
0.000000样例输入2
3 152 12 2样例输出2
0.0016840.9966320.001684题目来源
什么？你想用DFS？复杂度可能是O（4*120!），也就大概是
的复杂度。
所以，这道题很明显就是一道概率DP的题~
DP数组表示？
对于本题，不妨设 f[i][j][k][v] 表示1、2、3、4种生物的生命值为i、j、k、v的概率。
初始值？
很显然，对于读入的 a[1...n]，可以有 f[a[1]][a[2]][a[3]][a[4]]=1 （没有读入的生命值为0）
怎么转移？
对于a[1]+a[2]+a[3]+a[4]<=m的情况，直接输出n个0.000000即可。（难道这还用问为什么？）
若a[1]+a[2]+a[3]+a[4]>m，开始dp。
1 dp[a[1]][a[2]][a[3]][a[4]]=1; 2 for (register int i=a[1];i>=0;--i) 3 for (register int v=a[2];v>=0;--v) 4 for (register int k=a[3];k>=0;--k) 5 for (register int j=a[4];j>=0;--j) 6 { 7 if(a[1]-i+a[2]-v+a[3]-k+a[4]-j>m) continue; 8 register int cnt=0; 9 if(i)++cnt; if(v)++cnt; if(k)++cnt; if(j)++cnt;10 if(!cnt) continue;11 double gl=1.000000/(double)cnt;12 if(i) dp[i-1][v][k][j]+=gl*dp[i][v][k][j];13 if(v) dp[i][v-1][k][j]+=gl*dp[i][v][k][j];14 if(k) dp[i][v][k-1][j]+=gl*dp[i][v][k][j];15 if(j) dp[i][v][k][j-1]+=gl*dp[i][v][k][j];16 } 方程的含义是显而易见的。由当前状态推向下一状态，并乘以对应的概率。
如何求得答案？
举个栗子，对于一个对第一个生物生存的概率询问，我们遍历求和，sum=Σf[0][j][k][v]，其中j<=a[2],k<=a[3],v<=a[4],且 a[1]+a[2]-j+a[3]-k+a[4]-v==m
这样，我们求到的sum是第一个生物死亡的概率，我们回答 1.0-sum 即可。
附上AC代码
1 #include2 #include 3 using namespace std; 4 template inline void read(_T &_a) 5 { 6 char _ch=getchar();_a=0; 7 while(_ch<'0'||_ch>'9')_ch=getchar(); 8 while(_ch>='0'&&_ch<='9'){_a=(_a<<3)+(_a<<1)+_ch-'0';_ch=getchar();} 9 }10 11 const int maxn=5;12 int n,m,a[maxn];13 double dp[51][51][51][51];14 15 int main()16 {17 freopen("volcano.in","r",stdin);18 freopen("volcano.out","w",stdout);19 read(n); read(m);20 for (register int i=1;i<=n;++i) read(a[i]);21 if(m>=a[1]+a[2]+a[3]+a[4])22 {23 for (register int i=1;i<=n;++i) printf("0.000000\n");24 return 0;25 }26 dp[a[1]][a[2]][a[3]][a[4]]=1;27 for (register int i=a[1];i>=0;--i)28 for (register int v=a[2];v>=0;--v)29 for (register int k=a[3];k>=0;--k)30 for (register int j=a[4];j>=0;--j)31 {32 if(a[1]-i+a[2]-v+a[3]-k+a[4]-j>m) continue;33 register int cnt=0;34 if(i)++cnt; if(v)++cnt; if(k)++cnt; if(j)++cnt;35 if(!cnt) continue;36 double gl=1.000000/(double)cnt;37 if(i) dp[i-1][v][k][j]+=gl*dp[i][v][k][j];38 if(v) dp[i][v-1][k][j]+=gl*dp[i][v][k][j];39 if(k) dp[i][v][k-1][j]+=gl*dp[i][v][k][j];40 if(j) dp[i][v][k][j-1]+=gl*dp[i][v][k][j];41 }42 for (register int i=1;i<=n;i++)43 {44 register double ans=0;45 if (i==1)46 for (register int j=0;j<=a[2];++j)47 for (register int k=0;k<=a[3];++k)48 for (register int p=0;p<=a[4];++p)49 if (a[1]+a[2]-j+a[3]-k+a[4]-p==m)50 ans+=dp[0][j][k][p];51 if (i==2)52 for (register int j=0;j<=a[1];++j)53 for (register int k=0;k<=a[3];++k)54 for (register int p=0;p<=a[4];++p)55 if (a[1]-j+a[2]+a[3]-k+a[4]-p==m)56 ans+=dp[j][0][k][p]; 57 if (i==3)58 for (register int j=0;j<=a[1];++j)59 for (register int k=0;k<=a[2];++k)60 for (register int p=0;p<=a[4];++p)61 if (a[1]-j+a[2]-k+a[3]+a[4]-p==m)62 ans+=dp[j][k][0][p]; 63 if (i==4)64 for (register int j=0;j<=a[1];++j)65 for (register int k=0;k<=a[2];++k)66 for (register int p=0;p<=a[3];++p)67 if (a[1]-j+a[2]-k+a[3]-p+a[4]==m)68 ans+=dp[j][k][p][0]; 69 printf("%lf\n",1.000000-ans);70 }71 return 0;72 }