Ural 1167 Bicolored Horses：DP 分組最小化代價

Ural 1167 Bicolored Horses 題解

題目大意

n 匹馬排成一列，每匹馬為黑(0)或白(1)。需分成 k 組連續區間，每組內部代價 = (黑馬數) × (白馬數)。最小化總代價。
n ≤ 500, k ≤ n。

DP 狀態定義

• dp[i][j]：前 i 匹馬分成 j 組的最小代價
• 轉移：枚舉第 j 組的起始位置 h (0 ≤ h < i)
  dp[i][j] = min_{h < i} { dp[h][j-1] + cost(h+1, i) }

代價快速計算

預處理前綴和：sum0[i] = 前 i 匹黑馬數，sum1[i] = 白馬數。
區間 [l, r] 代價 = (sum0[r]-sum0[l-1]) * (sum1[r]-sum1[l-1])，O(1) 查詢。

完整程式碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 600;

int sum0[MAXN], sum1[MAXN];
int dp[MAXN][MAXN];
int color[MAXN];

int main() {
    int n, k;
    while (~scanf("%d%d", &n, &k)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &color[i]);
            sum0[i] = sum0[i-1] + (color[i] == 0);
            sum1[i] = sum1[i-1] + (color[i] == 1);
        }

        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;

        for (int i = 1; i <= k; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int h = 0; h < j; ++h) {
                    int c0 = sum0[j] - sum0[h];
                    int c1 = sum1[j] - sum1[h];
                    dp[j][i] = min(dp[j][i], dp[h][i-1] + c0 * c1);
                }
            }
        }
        printf("%d\n", dp[n][k]);
    }
    return 0;
}

複雜度分析

• 時間：O(k * n^2)，500^3 = 1.25e8 邊界較緊，但常數極小，C++ 通常能過
• 空間：O(n^2)

優化方向（可選）

• 決策單調性優化（分治 DP / 斜率優化）可降至 O(k n log n) 或 O(k n)
• 本題數據範圍下直接三重循環通常可通過