【CodeForces 261B】Maxim and Restaurant（DP，期望）
【CodeForces 261B】Maxim and Restaurant（DP，期望）
饶文津
发布于 2020-06-02 15:44:50
发布于 2020-06-02 15:44:50
第一种解法是O(n^3*p)的：f[i][j][k]表示前i个人进j个人长度为k有几种方案（排列固定为123..n时）。f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-a[i]]最外层枚举t表示被卡的那个人。i=t时不加上f[i-1][j-1][k-a[i]]。ans={{(\sum f[n][j][k]*j*j!*(n-1-j)!)+(\sum f[n][n][k]*n)}}/(n!)。
#include<cstdio>
#include<cstring>
#define N 55
int n,p,a[N];
double f[N][N][N],ans,c[N]= {1};
int main(){
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
c[i]=c[i-1]*i;
}
scanf("%d",&p);
for(int t=0; t<=n; t++){
memset(f,0,sizeof f);
f[0][0][0]=1;
for(int i=1; i<=n; i++)
for(int j=0; j<=i; j++)
for(int k=0; k<=p; k++){
f[i][j][k]=f[i-1][j][k];
if(j>=1&&t!=i&&k>=a[i])f[i][j][k]+=f[i-1][j-1][k-a[i]];
}
for(int j=1; j<n; j++)
for(int k=1; k<=p; k++)if(a[t]+k>p)
ans+=c[j]*c[n-1-j]/c[n]*f[n][j][k]*j;
for(int k=1; k<=p; k++)ans+=f[n][n][k]*n;
}
printf("%lf",ans);
}还可以更高效，O(n^2*p)参考题解
f[i][j][k]表示前i个人至少进j个人这j个人的长度和为k有几种方案（排列为123..n时）。那么ans=(\sum f[n][j][k]*j!*(n-j)!/(n!)。
我原来不太理解为什么至少j个人就是这么推，问了下队友，说是因为没有卡后面的，所以有可能可以进更多人。 其实第一种方法算的f也是至少j个人，然后在后面累加ans时再卡住第j+1个人。
并且可以用滚动数组优化为2维数组。
#include<cstdio>
#define N 51
int n,a[N],p;
double fac[N]= {1},f[N][N],tol,ans;
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",a+i);
fac[i]=fac[i-1]*i;
tol+=a[i];
}
scanf("%d",&p);
if(tol<=p)
{
printf("%d",n);
return 0;
}
f[0][0]=1;
for(int i=1; i<=n; i++)
for(int j=n-1; j>=0; j--)
for(int k=0; k+a[i]<=p; k++)
f[j+1][k+a[i]]+=f[j][k];
for(int j=1; j<=n; j++)
for(int k=0; k<=p; k++)
ans+=f[j][k]*fac[j]*fac[n-j];
ans/=fac[n];
printf("%lf",ans);
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-07-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读