题目大意：

手机在蜂窝网络中的定位是一个基本问题。如果蜂窝网络已经得知手机处于c1, c2,…,cn这些区域中的一个。最简单的方法是同一时候在这些区域中寻找手机。但这样做非常浪费带宽。因为蜂窝网络中能够得知手机在这不同区域中的概率。因此一个折中的方法就是把这些区域分成w组，然后依次訪问。比方。已知手机可能位于5个区域中，概率分别为0.3、0.05、0.1、0.3和0.25，w=2，则一种方法是先同一时候訪问{c1,c2,c3}，再同一时候訪问{c4,c5}，訪问区域数的数学期望为3*(0.3+0.05+0.1)+(3+2)*(0.3+0.25)=4.1。还有一种方法是先同一时候訪问{c1,c4}。再訪问{c2,c3,c5}，訪问区域数的数学期望为2×(0.3+0.3)+(3+2)×(0.05+0.1+0.25)=3.2。

解题思路：

由公式能够发现。为了让总期望值最小，应该让概率大的区域尽量放在前面去訪问。

所以先把全部概率从大到小排序一遍。然后分组时，就能够取连续的一段分为一组了。

f[i][j]表示: 前i个,分成j组的最小期望值

f[i][j] = min{ f[k-1][j] + i*sum[k~i], 1<=k<=i}

#include

#include

#include

using namespace std;

int main() {

int T;

scanf("%d", &T);

while (T--) {

int n, w;

double sum[110] = {0}, DP[110][110] = {0}, total = 0;

scanf("%d%d", &n, &w);

for (int i = 1; i <= n; i++) {

scanf("%lf", &sum[i]);

total += sum[i];

}

sort(sum + 1, sum + n + 1, greater());

for (int i = 1; i <= n; i++)

sum[i] = sum[i] / total + sum[i-1];

for (int i = 1; i <= n; i++) {

DP[i][0] = 0x3f3f3f3f;

for (int j = 1; j <= w; j++) {

DP[i][j] = 0x3f3f3f3f;

for (int k = 1; k <= i; k++)

DP[i][j] = min(DP[i][j], DP[k-1][j-1] + i * (sum[i] - sum[k-1]));

}

}

printf("%.4lf\n", DP[n][w]);

}

return 0;

}

查看原文