DP URAL 1167 Bicolored Horses

 1 /*  2    ：k   ，n  ，  1，   0，    unhappy  ：   *   ，    unhappy       3        ：dp[i][l] = min (dp[i][l], dp[i-1][j] + cur * (l - j - cur))    l      i  ，         4       dp   INF，           ，       5 */  6 #include <cstdio>  7 #include <iostream>  8 #include <algorithm>  9 #include <cstring> 10 #include <cmath> 11 using namespace std; 12 13 const int MAXN = 5e2 + 10; 14 const int INF = 0x3f3f3f3f; 15 int dp[MAXN][MAXN]; 16 int a[MAXN], sum[MAXN]; 17 18 int main(void) //URAL 1167 Bicolored Horses 19 { 20 //freopen ("L.in", "r", stdin); 21 22 int n, k; 23 while (scanf ("%d%d", &n, &k) == 2) 24  { 25 memset (sum, 0, sizeof (sum)); 26 for (int i=0; i<=k; ++i) 27 for (int j=0; j<=n; ++j) dp[i][j] = INF; 28 for (int i=1; i<=n; ++i) {scanf ("%d", &a[i]); sum[i] = a[i]; sum[i] += sum[i-1];} 29 30 dp[0][0] = 0; 31 for (int i=1; i<=k; ++i) 32  { 33 for (int j=0; j<=n; ++j) 34  { 35 for (int l=j+1; l<=n; ++l) 36  { 37 int cur = sum[l] - sum[j]; 38 dp[i][l] = min (dp[i][l], dp[i-1][j] + cur * (l - j - cur)); 39  } 40  } 41  } 42 43 printf ("%d
", dp[k][n]); 44  } 45 46 return 0; 47 }