题目描述

每天晚上，牧马人把所有马排在一条直线上带回马厩。由于马儿们很累，牧马人尽量不让它们移动。所以他发明了一个算法：他把前 P1 匹马放在第一个马厩，后 P2 匹马放在第二个马厩……而且，他不想 K 个马厩中的任何一个是空的，并且没有马被留在外边。

牧马人有黑白两种颜色的马，两种颜色的马相处不好。如果有 i 匹黑马和 j 匹白马同在一个马厩中，那么这个马厩的忧愁系数为 i × j，总忧愁系数是所有马厩的马的忧愁系数的和。忧愁系数过大会表现在马儿互相打架或者马儿彻夜长嘶。

请想方法把 N 匹马放进 K 个马厩，使得总忧愁系数最小。

输入格式

• 第一行是两个整数 N 和 K，表示马的总数和马厩的数量（1 ≤ N ≤ 500，1 ≤ K ≤ N）。
• 接下来的 N 行，每行是一个整数，表示每匹马的颜色：1 代表黑色，0 代表白色。

输出格式

• 输出一个整数，表示最小的总忧愁系数。

样例输入

6 3
1
1
0
1
0
1

样例输出

2

样例说明

将前 2 匹马放在第一个马厩，随后 3 匹马放在第二个马厩，最后一匹马放在第三个马厩。此时，忧愁系数为 2，是最小的。

解题思路

这是一道区间型的动态规划题目。我们的目标是分配马到马厩，并最小化总的忧愁系数。每个马厩中的忧愁系数是通过该马厩中的黑白马数量计算的，忧愁系数的计算为 i × j，其中 i 是黑马的数量，j 是白马的数量。

动态规划状态定义

• dp[i][j] 表示前 i 个马厩分配了 j 匹马的最小总忧愁系数。
• b[] 数组为黑马的前缀和，表示前 i 匹马中有多少匹黑马。

动态转移方程

• 对于每个 dp[i][j]，我们需要从前一个马厩的所有可能的分配 k 匹马过来，计算当前分配的最小忧愁系数： dp[i][j]=min⁡(dp[i−1][k]+(b[j]−b[k])×(j−k−(b[j]−b[k])))dp[i][j] = \min(dp[i-1][k] + (b[j] - b[k]) \times (j - k - (b[j] - b[k]))) 其中，(b[j] - b[k]) 是当前马厩中黑马的数量，(j - k - (b[j] - b[k])) 是白马的数量。

边界条件

• f[0][0] = 0，没有马的情况下，忧愁系数为 0。
• f[i][i] = 0，将 i 匹马放进 i 个马厩，每个马厩一个马，不会有忧愁系数。

复杂度分析

• 时间复杂度为 O(N^2 * K)，其中 N 是马的数量，K 是马厩的数量。
• 空间复杂度为 O(N * K)，用于存储动态规划的状态。