做网上购物网站,汽车网站建设制作费用,湖南装修公司排名10名,wordpress头像网站正题
题目链接:https://www.luogu.com.cn/problem/AT3860 题目大意
有一个周长为mmm的圆#xff0c;nnn条线段#xff0c;第iii条长度为aia_iai#xff0c;将线段贴在圆的随机位置上#xff0c;求整个圆都被覆盖的概率。 1≤n≤6,1≤m≤501\leq n\leq 6,1\leq m\le 501…正题
题目链接:https://www.luogu.com.cn/problem/AT3860 题目大意
有一个周长为mmm的圆nnn条线段第iii条长度为aia_iai将线段贴在圆的随机位置上求整个圆都被覆盖的概率。
1≤n≤6,1≤m≤501\leq n\leq 6,1\leq m\le 501≤n≤6,1≤m≤50 解题思路
这种随机实数的问题我们可以从排名方面考虑。
先固定最长的一条线不动且左端点作为起点就可以不需要考虑环的问题了然后对于每条线的开头离上一个整点的距离ddd进行一个排序就可以作为每条线的排名了。
具体地我们枚举一个排列作为排名那这样就变为了n×mn\times mn×m个点每个排名考虑用dpdpdp解决问题。
首先我们需要记录线段的使用状态然后我们一个一个位置考虑线段是否填然后还需要目前延伸到的最末尾位置。
设fl,r,sf_{l,r,s}fl,r,s表示目前填到lll最远延伸到rrr线段使用状态为sss时的概率然后因为我们线段开头的排名是确定的所以对于一个lll只能有一条线段可以填可以省去枚举这条线段的时间。
时间复杂度O(n2m22nn!)O(n^2m^22^nn!)O(n2m22nn!)
实际上常数很小可以通过本题 code
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const double eps1e-9;
int n,m,cnt,a[10];
double ans,f[500][70];
int main()
{freopen(circle.in,r,stdin);freopen(circle.out,w,stdout);scanf(%d%d,n,m);for(int i0;in;i)scanf(%d,a[i]),a[i]a[i]*n;sort(a,an);do{int MS(1n-1);for(int i0;in*m;i)for(int s0;sMS;s)f[i][s]0;f[a[n-1]][0]1;for(int i1;in*m;i){if(i%n0)continue;int xi%n-1;for(int ji;jn*m;j){for(int s0;sMS;s){if(f[j][s]eps||((sx)1))continue;f[min(n*m,max(j,ia[x]))][s|(1x)]f[j][s];}}}ansf[n*m][MS-1];cnt;}while(next_permutation(a,an-1));printf(%.12lf,ans/(double)cnt/pow(m,n-1));return 0;
}
