UVA1456 Cellular Network 题解
夭寿了！30 行写完紫题了！
更新：已联系管理员修改难度，现在是绿题
题意很简单，不再赘述。
首先一个小贪心，将概率 \(u\) 进行从大到小的排序，优先查看概率大的区域，显然这样能够保证访问数量期望最小。
接着考虑如何将区域分组。一个显而易见的思路是动态规划。
记 \(f_{i,j}\) 表示前 \(i\) 个区域被分成 \(j\) 组，并全部访问完后期望的最小值。
则有如下转移：
\[f_{i,j} = \min\limits_{0 \le k < i}\{f_{k, j - 1} + \sum\limits_{x =k + 1}\limits^{i}u_x\} \]求个前缀和可以在 \(O(n)\) 内完成转移。总时间复杂度为 \(O(n^2w)\)，完全足够通过本题。
代码如下：
#include<bits/stdc++.h>
#define MAXN 110
using namespace std;
typedef long long ll;
int t, n, w;
ll u[MAXN], sum[MAXN], dp[MAXN][MAXN];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&w);
for(int i = 1; i <= n; i++) scanf("%d",&u[i]);
sort(u + 1, u + n + 1, greater<int>());
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + u[i];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= i; j++){
for(int k = 1; k <= w; k++){
dp[i][k] = min(dp[i][k], dp[j][k - 1] + i * (sum[i] - sum[j]));
}
}
}
printf("%.4f\n",dp[n][w] * 1.0 / sum[n]);
}
}