链接
传送门
大意
手机蜂窝数据可以得到手机在\(n\)个地方的概率，\(p_i\)。现在要查询手机的位置，可以分成\(w\)组，分别查询，输出查询次数的期望值的最小值。
思路
要使查询次数最小，应该优先查找存在概率高的地点，先对位置排序。然后设状态\(d[i][j]\)为前\(i\)个地点，分成\(j\)组查询的最小期望。对于每个状态，可以通过枚举最后一组的大小进行转移。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
double a[maxn], sum, f[maxn][maxn];
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, w, sum = 0;
scanf("%d%d", &n, &w);
for (int i = 1; i <= n; ++i) {
scanf("%lf", &a[i]);
sum += a[i];
}
sort(a + 1, a + n + 1, greater<int>());
for (int i = 1; i <= n; ++i) {
a[i + 1] += a[i];
a[i] /= sum;
}
for (int i = 1; i <= n; ++i) {
f[i][0] = inf;
for (int j = 1; j <= w; ++j) {
f[i][j] = inf;
for (int k = j; k <= i; ++k) {
f[i][j] = min(f[i][j], f[k - 1][j - 1] + i * (a[i] - a[k - 1]));
}
}
}
printf("%.4f\n", f[n][w]);
}
return 0;
}
|