농장주 농장주

제목.

장 군은 말을 기르는 농장의 농장주이다. 그는 N 마리의 말을 K 개의 마방에 배치하려고 한다. 방치하는 규칙은 첫 번째 말부터 첫 번째 마방에 넣고, 첫 번째 Pi+1에서 두 번째 마방에 넣는다. 이런 식으로 유추한다.또한 각 마방마다'불쾌계수'라는 이름이 있는데 그것이 바로 흰색 말의 수량 * 검은색 말의 수량이다.너의 임무는 이 N 마리의 말을 합리적으로 분배해서 모든 마방의 '불쾌 계수' 와 가장 작게 하는 것이다.

입력

파일i n farmer.in farmer.in에서 데이터를 읽으면 파일의 첫 번째 줄에 222개의 정수가 있습니다: $N (1 < = N < = 500) $및 K (1 < = K < = N) K (1 < = K < = N) K (1 < = K < = N) 다음 N 줄에 N 수가 있습니다.I행동 I마리의 말 색깔: 1은 검은색, 0은 흰색.

출력

결과를 파일 fa r m e r로 출력합니다.o u t farmer.out farmer.out에서 그 결과는 가장 작은'불쾌 계수'의 총체이다

샘플 가져오기

farmer.in
6 3
1
1
0
1
0
1

출력 예제

farmer.out
2

문제풀이의 방향

이 문제는 우리가 DP로 f[i,j]를 사용하여 i개의 마방에 j말을 싣는 가장 작은 불쾌 계수를 나타낸다. 우선 i번째 말을 처리할 때 몇 마리의 백마가 있는지, 몇 마리의 검은 말이 DP에 이어가는지, 소마방에 말을 싣고 다마방에 말을 싣는 것을 갱신해야 하기 때문에 동적 이동 방정식은

a n s = m i n ( a n s , f [ i − 1 ] [ k ] + ( b l a c k [ j ] − b l a c k [ k ] ) ∗ ( w h i t e [ j ] − w h i t e [ k ] ) ) ans = min(ans, f[i - 1][k] + (black[j] - black[k]) * (white[j] - white[k])) ans=min(ans,f[i−1][k]+(black[j]−black[k])∗(white[j]−white[k]))

절차는 다음과 같다.

#include
#include
#include
#include

using namespace std;

int n, k, ans;

int a[10001], white[10001], black[10001], f[10001][1001];

int main()
{
	freopen("farmer.in","r",stdin);
	freopen("farmer.out","w",stdout);
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		if(a[i] == 1)
		{
			white[i] = white[i - 1];
			black[i] = black[i - 1] + 1; //   
		}
		else
		{
			white[i] = white[i - 1] + 1;
			black[i] = black[i - 1]; 
		}	
	}
	for(int i = 1; i <= n; ++i)
		f[1][i] = white[i] * black[i];//  
	for(int i = 2; i <= k; ++i)
		for(int j = i; j <= n - k + i; ++j)
		{
			ans = 2147483647;
			for (int k = i - 1; k <= j - 1; ++k)
				ans = min(ans, f[i - 1][k] + (black[j] - black[k]) * (white[j] - white[k]));//            
			f[i][j] = ans;
		}
	printf("%d",f[k][n]);
	return 0;
}