Description
给定一个数a0, 并给出定义:序列a1,a2,a3…
1.从闭区间[0,a0]中等概率随机选择一个整数k0,令a1=a0-k0
2.得到随机数a1后，再从闭区间[0,a1]中等概率随机选择一个整数k1,令a2=a1-k1
3.一般地，得到随机数ai后，再从闭区间[0,ai]中等概率随机选择一个整数ki,令a(i+1) = ai- ki
问经过n步后，an==0的概率是多少呢？
Input
输入两个正整数n,a0
(1<=n,a0<=100)
Output
输出概率，小数点后四舍五入保留5位小数
Sample Input 1
3 3
Sample Output 1
0.72049
思路：dp[x][y]代表第x层选择y得到0的概率。然后记忆化就可以了。具体看代码：
提交链接
代码如下：
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxx=1e2+10; double dp[maxx][maxx]; int n,m; inline double dfs(int x,int y) {if(dp[x][y]!=-1.0) return dp[x][y];if(x<0) return 0.0;if(y==0) return dp[x][y]=1.0;double sum=0.0;for(int i=0;i<=y;i++){double num=dfs(x-1,y-i)/(double)(y+1);sum+=num;}return dp[x][y]=sum; } int main() {scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=-1.0;printf("%.5lfn",dfs(n,m));return 0; }
12345678910111213141516171819202122232425262728努力加油a啊，(o)/~
