농장주 농장주

제목.

장 군은 말을 기르는 농장의 농장주이다. 그는 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;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다