题解：UVA1456 Cellular Network

檀溪的小窝 / 2024-09-27 / 原文

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]);
    } 
}