Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A cellular network is a radio network made up of a number of cells each served by a base station located in the cell. The base station receives call signals from mobile users (mobiles) in the cell it serves, which then connects the calls to the wired land-line telephone network. When a call is requested to connect to a mobile, the cellular network must know in which cell the mobile is located so that the call is routed to the base station of the cell appropriately.

Mobiles move from once cell to another in a cellular network. Whenever a mobile reports its new cell as it crosses boundaries of cells, the cellular network would know its exact cell at any time and finding (paging) the mobile becomes a trivial task. But it is usually infeasible for a mobile to report its new location each time it enters a new cell because of the insufficiencies of resources such as the radio bandwidth. But normally at the time of a call arrival, the cellular network knows a limited number of cells where the mobile is located. In this situation, a lot of paging strategies are developed to locate a mobile efficiently. The ultimate goal of paging strategies is to minimize both the time delay and cost of paging until the mobile is found.

Now we define our problem formally. The location area is the set of n cells C = {c₁, c₂,..., c_n} such that the mobile is guaranteed to be in one of these cells at the time of a call arrival. Suppose that it is possible to page any subset of these n cells in a unit of time (paging rounds) and find out if the mobile is located in one of the cells paged. The fastest strategy to find the cell where the mobile is located is to page all the n cells in the first and only round. However this strategy uses a lot of wireless bandwidth.

In many cases, the cellular network knows about the whereabouts of the mobile. This knowledge can be modeled with n probability values, where the probability of the mobile being present in a cell can be estimated for each of these n cells at the time of a call arrival. Let p_i be the probability that the mobile is located at the cell c_i and all the probabilities are independent. A sequential paging strategy is to page the cells sequentially in n paging rounds terminating once the mobile is found. Then the average cost of paging (number of cells paged), , and the average paging delay (number of paging rounds) in locating the mobile, , can be expressed as follows:

The parallel paging strategy is to page the cells in a collection of cells simultaneously. Sequential paging strategy has lower paging cost than parallel paging strategy, but at the expense of larger paging delay. The method of parallel paging is to partition the cells in a location area into a series of indexed groups referred to as paging zones. Let Z₁, Z₂,..., Z_w be the partition of the location area C (i.e., a partition of C into w groups), where each Z_i is non-empty and corresponds to a distinct paging zone. When a call arrives for a mobile, the cells in the first paging zone Z₁ are paged simultaneously in the first round and then if the mobile is not found in the first round of paging, all the cells in the second paging zone Z₂ are paged, and so on. Let the number of cells in the paging zone Z_i be denoted by n_i = | Z_i|, and let be the corresponding zone probabilities of the users in the paging zone Z_i, where = p_j. Then the average cost of paging (number of cells paged), , and the average paging delay (number of paging rounds) in locating the mobile, D, can be expressed as follows:

In parallel paging strategy, there is a tradeoff between bandwidth for time. For example, we increases the number of paging zones, then the paging cost could be decreased. If we decrease the number of paging zones, then the paging cost could be increased. Furthermore, for a fixed number w of paging zones, the paging cost could be different to the strategies how the cells in location area are partitioned.

For example, there are n = 5 cells in a location area C = {c₁, c₂,..., c₅} and the probability of each cells in C are as follows:

If the cells in C are partitioned into two paging zones Z₁ = {c₁, c₂, c₃}, Z₂ = {c₄, c₅}, the average cost of paging, , and the average paging delay in locating the mobile, , are:

= n₁ + (n₁ + n₂) = 3(0.3 + 0.05 + 0.1) + (3 + 2)(0.3 + 0.25) = 3 x 0.45 + 5 x 0.55 = 4.1

= 1 +2 = 1(0.3 + 0.05 + 0.1) + 2(0.3 + 0.25) = 1 x 0.45 + 2 x 0.55 = 1.55

If the cells in C are partitioned into two paging zones Z₁ = {c₁, c₄}, Z₂ = {c₂, c₃, c₅}, the average cost of paging, , and the average paging delay in locating the mobile, , are:

= n₁ + (n₁ + n₂) = 2(0.3 + 0.3) + (3 + 2)(0.05 + 0.1 + 0.25) = 2 x 0.6 + 5 x 0.4 = 3.2

= 1 +2 = 1(0.3 + 0.3) + 2(0.05 + 0.1 + 0.25) = 1 x 0.6 + 2 x 0.4 = 1.4

Given the number of cells in a location area C, the probabilities of each cells that a mobile is located at the cell, and the fixed number w of paging zones, write a program to partition the cells in C into w paging zones such that the average cost of paging to find the location of the mobile is minimized.

Input 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of two lines. The first line of each test case contains two integers. The first integer, n, is the number of cells in a location area, and the second integer, w, is the number of paging zones, where 1wn100. The second line of each test case contains n integers u₁, u₂,..., u_n, where the probability p_i for each cell c_i in C is p_i = u_i/(u₁ + u₂ + ^... + u_n). All integers in the second line are between 1 and 10,000.

Output 

Your program is to write to standard output. Print exactly one line for each test case. The line should contain the minimum average cost of paging to find the location of the mobile. The output should have a precision of exactly 4 digits after decimal point. You may round to the 4 digits after decimal point or round off at the 4-th digit after decimal point.

The following shows sample input and output for two test cases.

Sample Input 

2 
5 2 
30 5 10 30 25 
5 5 
30 5 10 30 25

Sample Output 

3.2000 
2.3000

---

這一題只求 C 的最小值, 那麼C的公式計算

 = n1 + (n1 + n2) ... 類推, 很明顯的, 
我們可以知道如果從Z1, Z2 ... 的集合元素排成一列, 一定是由大到小排列, 才會產生最小值,
接著我們去進行將一排的數字切成 w 段, 如果之前有寫過 "最大值最小化問題" 這一題的 dp 方程就不難理解,

dp[i][j] 代表 前 i 個數字分成 j 段的最小值

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

#include <cstdio>
#include <cstring>
#include <functional>
#include <algorithm>
using namespace std;
int main() {
    int t, n, w, u[105];
    int dp[105][105];
    int i, j, k;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &w);
        for(i = 1; i <= n; i++)
            scanf("%d", &u[i]);
        sort(u+1, u+n+1, greater<int>());
        memset(dp, 63, sizeof(dp));
        int sum[105] = {};
        for(i = 1; i <= n; i++)
            sum[i] = sum[i-1]+u[i];
        dp[0][0] = 0;
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= w; j++) {
                for(k = 0; k < i; k++) {
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + i*(sum[i]-sum[k]));
                }
            }
        }
        printf("%.4lf\n", dp[n][w]/(double)sum[n]);
    }
    return 0;
}