这题纠结好久了 看一神代码 想了N久才明白它的意思
dp[i][j]表示放了i个数后和为J的方式有多少种
而在算阶层总数的时候 会重一部分 而重的那一部分恰好为小于等于P的长度 所以就直接省了乘长度这一部分
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define LL long long 9 int a[55];10 LL dp[55][55];11 double pp[55];12 int main()13 {14 int i,j,k,n,p;15 scanf("%d",&n);16 for(i = 1; i <= n ; i++)17 scanf("%d",&a[i]);18 scanf("%d",&p);19 dp[0][0] = 1;20 for(i = 1; i <= n ;i++)21 for(j = n ; j>=1 ; j--)22 for(k = p ; k >= a[i] ; k--)23 {24 dp[j][k] += dp[j-1][k-a[i]];25 }26 pp[0] = 1;27 for(i = 1; i <= n ;i++)28 pp[i] = pp[i-1]*i;29 double ans=0;30 for(i = 0 ;i <= n ; i++)31 {32 for(j = 1 ; j <= p ; j++)33 {34 ans+=pp[i]*pp[n-i]*dp[i][j];35 }36 }37 printf("%.8lf\n",ans/pp[n]);38 return 0;39 }