This post is written in Chinese. Please consider using Google Translate

动态规划，由于是马进入马厩连续的，要先预处理求出每个连续序列的马进入一个马厩的不快乐值。然后以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;
}