URAL 1167. Bicolored Horses dp

1167. Bicolored Horses

6 3
1
1
0
1
0
1

2

//0.125	2 202 KB
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int h[507],dp[507][507],unhappy[507][507];
int main()
{
    int n,kk;
    while(scanf("%d%d",&n,&kk)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&h[i]);
        memset(unhappy,0,sizeof(unhappy));
        for(int i=1;i<=n;i++)dp[0][i]=inf;
        int b,w;
        for(int i=1;i<=n;i++)//预处理每段区间的不愉快值
        {
            b=0;w=0;
            for(int j=i;j<=n;j++)
            {
                if(h[j])b++;else w++;
                unhappy[i][j]=b*w;
            }
        }
        for(int i=1;i<=kk;i++)//k个马槽
            for(int j=1;j<=n;j++)//前j匹马
            {
                dp[i][j]=inf;
                for(int k=1;k<=j;k++)//枚举前j匹马
                    dp[i][j]=min(dp[i][j],dp[i-1][k-1]+unhappy[k][j]);
            }
        printf("%d\n",dp[kk][n]);
    }
    return 0;
}