24687: 封锁管控

http://cs101.openjudge.cn/practice/24687/

为减少人员流动，降低疫情传播风险，某城市决定在内部施加封锁管控措施。

为方便讨论，假设城市为一条线段，从左至右排布了 n 个居民区，第 i 个居民区中住有 ai 个人。现在要建设 m(m<n) 个“管控点”（可视为墙），每个管控点设在相邻两个居民区之间，使得居民的活动不能跨越该管控点。

定义“人口流动指数”为每个居民（从其原住区）能到达的居民区个数的总和。求在建设 m 个管控点后，人口流动指数最小为多少？

例如，5个居民区被1个管控点隔开（数字表示居民区的人数）：

10 50 | 20 30 40

则此时的人口流动指数为 (10 + 50) * 2 + (20 + 30 + 40) * 3 = 390 。

输入

输入有两行。第一行为两个正整数n, m（n<=100）；第二行有n个数，表示每个居民区的人数ai（ai<=1000），用空格隔开。

输出

输出只有一行。一个正整数表示人口流动指数的最小值。

样例输入

5 1
10 50 20 30 40

样例输出

提示

对样例的解释：在第三个和第四个居民区间设管控点，此时人口流动指数为 (10+50+20)*3+(30+40)*2=380。

为了找到最小的人口流动指数，我们需要确定在哪里建立管控点才能最大限度地减少人口流动。一个朴素的方法是考虑所有可能的管控点设置，然后选择人口流动指数最小的设置。但是，这样做的时间复杂度是非常高的，特别是当居民区数量较多时。

我们可以使用动态规划来解决这个问题。我们可以定义一个动态规划数组 dp[i][j] 表示前 i 个居民区建立 j 个管控点后的最小人口流动指数。

状态转移方程如下：

dp[i][j] = min(dp[k][j-1] + sum[k+1 to i] * (i-k)) 对于所有 k < i

其中 sum[k+1 to i] 表示从居民区 k+1 到居民区 i 的人口数总和。

这样，最终答案将是 dp[n][m]。

python

def min_population_flow(n, m, populations):
    # Initialize the prefix sum array for fast range sum computation
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + populations[i - 1]
    
    # Initialize the DP table
    dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
    
    # Base case: with 0 control points, the flow index is just the sum of all populations times their district count
    for i in range(1, n + 1):
        dp[i][0] = prefix_sum[i] * i
    
    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, min(i, m) + 1):
            for k in range(j-1, i):
                dp[i][j] = min(dp[i][j], dp[k][j-1] + (prefix_sum[i] - prefix_sum[k]) * (i - k))
    
    # The answer is the minimum flow index after setting up m control points
    return dp[n][m]

# Input
n, m = map(int, input().split())
populations = list(map(int, input().split()))

# Output
print(min_population_flow(n, m, populations))

24687: 封锁管控 ​

24687: 封锁管控