Bicolored Horses

大意：给你N匹马，K个马厩，每一个马都只会是0或1，每一个马厩里会有一个不快乐值（不快乐值=0马的个数*1马的个数），问怎么分配会得出一个最小的不快乐值，输出最小的不快乐值。

思路：先（n^2）处理出来每个区间中的不快乐值，再用DP求解出K个马厩的最小不快乐值。

dp[i][j], i表示当前是分配的第几个马厩，j表示当前分配的是第几个马。

/*************************************************************************
> File Name: URAL1167.cpp
> Author: GLSilence
> Created Time: 2014年07月29日 星期二 08时30分30秒
************************************************************************/

#include
  
   
#include
   
     using namespace std; const int INF = 0x7ffffff; int a[505]; int b[505][505], c[505][505]; int sum[505][505]; int dp[505][505]; int main() { int n, k; scanf("%d%d", &n, &k); for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); dp[0][i]= INF; } for(int i = 1; i <= n; ++i){ for(int j = i; j <= n; ++j){ if(a[j] == 0){ b[i][j] = b[i][j-1]+1, c[i][j] = c[i][j-1]; } else{ b[i][j] = b[i][j-1], c[i][j] = c[i][j-1]+1; } sum[i][j] = b[i][j]*c[i][j]; } } int p; for(int i = 1; i <= k; ++i){ for(int j = 1; j <= n; ++j){ int Min = INF; for(int t = 1; t <= j; ++t){ p = dp[i-1][t-1]+sum[t][j]; Min = min(Min, p); } dp[i][j] = Min; } } printf("%d\n", dp[k][n]); return 0; }