動態規劃，由於是馬進入馬廄連續的，要先預處理求出每個連續序列的馬進入一個馬廄的不快樂值。然後以O(N^2*K)時間複雜度DP。

設A[0][i]爲前i匹馬中種類爲0的馬的數量，A[1][i]爲前i匹馬中種類爲1的馬的數量。則一個區間[i,j]內的馬進入一個馬廄的不快樂度U[i,j]爲 U[i,j]=( A[0][j] - A[0][i-1] ) * ( A[1][j] - A[1][i-1] )

動態規劃狀態設定 F[i,j]表示前i個馬廄，進入前j匹馬的最小不快樂度。

狀態轉移方程 F[i,j]=min{ F[i-1,k] + U[k+1,j] | k=0..j-1 }

邊界條件 F[0,0]=0 F[0,i]=MAX (i=1..N)

目標解 F[K,N]

以下是程序代碼

#include <iostream>

using namespace std;

const int MAX=501;
const int INF=0x7FFFFFF;

int N,K;
int Q[MAX],A[2][MAX];
int F[MAX][MAX];

void init()
{
    int i;
    freopen("1167.in","r",stdin);
    freopen("1167.out","w",stdout);
    scanf("%d%d",&N,&K);
    for (i=1;i<=N;i++)
    {
        scanf("%d",&Q[i]);
        A[0][i]=A[0][i-1];
        A[1][i]=A[1][i-1];
        if (Q[i]==0)
            A[0][i]++;
        else
            A[1][i]++;
        F[0][i]=INF;
    }
}

inline int U(int i,int j)
{
    return (A[0][j]-A[0][i-1])*(A[1][j]-A[1][i-1]);
}

void dynamic()
{
    int i,j,k,t,min,u;
    for (i=1;i<=K;i++)
    {
        for (j=1;j<=N;j++)
        {
            min=INF;
            for (k=0;k<=j-1;k++)
            {
                u=U(k+1,j);
                t=F[i-1][k] + u;
                if (t<min)
                    min=t;
            }
            F[i][j]=min;
        }
    }
}

int main()
{
    init();
    dynamic();
    cout << F[K][N] << endl;
    return 0;
}