首页 > 代码库 > URAL 1167 Bicolored Horses(DP)

URAL 1167 Bicolored Horses(DP)

2024-07-14 13:17:54   231人阅读

Bicolored Horses

 

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

 

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

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

 

 1 /************************************************************************* 2 > File Name: URAL1167.cpp 3 > Author: GLSilence 4 > Created Time: 2014年07月29日 星期二 08时30分30秒 5 ************************************************************************/ 6  7 #include<stdio.h> 8 #include<iostream> 9 using namespace std;10 const int INF = 0x7ffffff; 11 12 int a[505];13 int b[505][505], c[505][505];14 int sum[505][505];15 int dp[505][505];16 17 int main()18 {19     int n, k;20     scanf("%d%d", &n, &k);21     for(int i = 1; i <= n; ++i){22         scanf("%d", &a[i]);23         dp[0][i]= INF;24     }25 26     for(int i = 1; i <= n; ++i){27         for(int j = i; j <= n; ++j){28             if(a[j] == 0){29                 b[i][j] = b[i][j-1]+1, c[i][j] = c[i][j-1];30             }31             else{32                 b[i][j] = b[i][j-1], c[i][j] = c[i][j-1]+1;33             }34 35             sum[i][j] = b[i][j]*c[i][j];36         }37     }38     int p;39     for(int i = 1; i <= k; ++i){40         for(int j = 1; j <= n; ++j){41             int Min = INF;42             for(int t = 1; t <= j; ++t){43                 p = dp[i-1][t-1]+sum[t][j];44                 Min = min(Min, p);45             }46             dp[i][j] = Min;47         }48     }49     printf("%d\n", dp[k][n]);50 51     return 0;52 }
URAL 1167

 


联系
我们