【YBT2022寒假Day7 C】【luogu CF603E】以线覆圆 / Arcs on a Circle(期望)(DP)
以线覆圆 / Arcs on a Circle
题目链接:YBT2022寒假Day7 C / luogu AT3860
题目大意
给你一个周长为 n 的圆和一些长度的线段。
然后每条线段会随机出现在圆中,然后问你这些线段把整个圆覆盖的期望。
思路
我们首先考虑如果线段端点只能是整数,那我们不难有个方法:断环为链来 DP。(然后为了保证不重,我们保证第一个线段用的一定是最长的,并从这里开始)
然后如果我们不断提高他的精度,那这个 DP 就是对的。
然后你会发现它这个 DP 好像没有必要这个精度,好像我们只要确定这些点之间的相对关系即可。
(而且因为是实数,所以是可以认为两个点在同一位置的概率为
0
0
0)
然后我们可以把它变成
n
∗
c
n*c
n∗c 个点,我们考虑 DP:
首先我们要确定这些线段在小数部分的相对关系,所以要用
n
!
n!
n! 搞个全排列。
f
i
,
j
,
k
f_{i,j,k}
fi,j,k 为看到第
i
i
i 个点,然后已经覆盖到了
j
j
j 点,线段用的状态时
k
k
k。
然后我们就考虑当前点对应的线段在不在这里用,转移是
O
(
1
)
O(1)
O(1) 的。
然后就可以了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int c, n, l[7], xl[7], t;
double ans, f[301][32];
double ksm(double x, int y) {
double re = 1;
while (y) {
if (y & 1) re = re * x;
x = x * x;
y >>= 1;
}
return re;
}
int main() {
// freopen("circle.in", "r", stdin);
// freopen("circle.out", "w", stdout);
scanf("%d %d", &n, &c); t = 1;
for (int i = 1; i <= n; i++) {
xl[i] = i; t = t * i;
scanf("%d", &l[i]);
}
sort(l + 1, l + n + 1);
for (int qq = 1; qq <= t; qq++) {
memset(f, 0, sizeof(f));
f[l[n] * n][0] = 1;
for (int i = 1; i <= n * c; i++) {
if (i % n == 0) continue; int pl = i % n;
for (int j = i; j <= n * c; j++)
for (int k = 0; k < (1 << (n - 1)); k++) {
if ((k >> (pl - 1)) & 1) continue;
f[min(n * c, max(j, i + l[xl[pl]] * n))][k | (1 << (pl - 1))] += f[j][k];
}
}
ans += f[n * c][(1 << (n - 1)) - 1];
next_permutation(xl + 1, xl + n);
}
printf("%.16lf", ans / ksm(c, n - 1) / t);
return 0;
}
相关文章
- Installing on Windows anaconda
- How to specify data attributes in razor, e.g., data-externalid="23151" on @this.Html.CheckBoxFor(...)
- GH001 on github
- git fatal: https://github.com/TeaCodie/TeaCodie-Website.git/info/refs not found: did you run git update-server-info on the server 错误
- “Ubuntu on Windows” 初体验
- [LeetCode] Max Points on a Line
- opatch on-line patch and standby-fisrt patch
- 关键字: on
- 【SPOJ QTREE2】QTREE2 - Query on a tree II(LCA)
- IOS 被拒 关于 iPhone running iOS 10.3.1 on Wi-Fi connected to an IPv6 network.
- C#-linq join on 后多个条件怎么写