Codeforces Round #612 (Div. 2) C. Garland

문제 링크 : Problem - C - Codeforces

Problem - C - Codeforces

 

Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of nn light bulbs in a single row. Each bulb has a number from 1 to n (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by 2). For example, the complexity of 1 4 2 3 5 is 2 and the complexity of 1 3 5 7 6 4 2 is 1.

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.

Input

The first line contains a single integer n (1≤n≤100) — the number of light bulbs on the garland.

The second line contains n integers p1, p2, …, pn(0≤pi≤n) — the number on the ii-th bulb, or 0 if it was removed.

Output

Output a single number — the minimum complexity of the garland.

---

다이나믹 프로그래밍 문제이다.

학회 스터디를 통해 다이나믹 프로그래밍으로 해결이 가능하다는 것을 알았고 4차원 dp 배열을 사용하였다.

 

우선 dp[100][100][100][2] 를 설정한다. (O(2 * n^3) 으로 해결 가능)

dp[a][b][c][d] = a번째의 숫자를 놓거나 놓였을 때, 현재까지 짝수 b 개와 홀수 c 개를 놓았을 때의 최소 complexity 로 설계할 수 있다. (이때 d = 0 일 경우 a 번째의 숫자는 짝수, 1 일 경우 홀수)

 

4차원 dp 테이블을 채우는 방법은 다음과 같다.

 

① 우선, 최소 complexity 에 대한 값을 구하기 위해 테이블 값 전부 INF 로 초기화한다.

 

for (int i = 0; i <= n; i++)
	for (int j = 0; j <= n; j++)
		for (int k = 0; k <= n; k++)
			dp[i][j][k][0] = dp[i][j][k][1] = INF;

 

② 배열 p의 i 번째에 0 에 짝수, 홀수를 채워넣을 수 있는 숫자를 결정한다.

 

int even = 0, odd = 0;
for (int i = 1; i <= n; i++)
{
	if (check[i]) continue;
	if (i % 2) odd++;
	else even++;
}

 

③ 첫 시작을 dp[0][0][0][0] = dp[0][0][0][1] = 0 으로 설정하여 조건 2가지에 따라 dp 테이블을 따로 채우도록 한다.

 

(1) p[i] > 0 일 경우

• p[i] 가 짝수일 때 : dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1), 이전 숫자가 짝수였을 때는 유지하고, 이전 숫자가 홀수였을 때는 서로 다른 패리티가 되므로 1 증가시킨다.
• p[i] 가 홀수일 때 : dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]), 이전 숫자가 짝수였을 때는 서로 다른 패리티가 되므로 1 증가시키고, 이전 숫자가 홀수였을 때는 유지한다.

 

(2) p[i] == 0 일 경우

• 짝수를 놓을 경우 : dp[i][j][k][0] = min(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1] + 1), 이전 숫자가 짝수였을 때는 유지하고, 이전 숫자가 홀수였을 때는 서로 다른 패리티가 되므로 1 증가시킨다.
• 홀수를 놓을 경우 : dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]), 이전 숫자가 짝수였을 때는 서로 다른 패리티가 되므로 1 증가시키고, 이전 숫자가 홀수였을 때는 유지한다.

 

dp[0][0][0][0] = dp[0][0][0][1] = 0;
for (int i = 1; i <= n; i++)
{
	for (int j = 0; j <= even; j++)
	{
		for (int k = 0; k <= odd; k++)
		{
			if (p[i])
			{
				if (p[i] % 2)
					dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
				else
					dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1);
			}
			else
			{
				if (j - 1 >= 0)
					dp[i][j][k][0] = min(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1] + 1);
				if (k - 1 >= 0)
					dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]);
			}
		}
	}
}

 

④ 마지막에 숫자가 놓이지 않을 경우를 대비해서 min(dp[n][even][odd][0], dp[n][even][odd][1]) 가 결국 답이된다.

만약 n 번째에 숫자가 놓였을 경우 n 번째가 홀수였을 경우 dp[n][even][odd][1], 짝수였을 경우 dp[n][even][odd][0] 가 답이 되지만, ① 에서 INF 으로 초기화했기 때문에 둘 중 하나는 INF 가 되므로 위와 같이 두 값중 최소값을 출력하면 된다.

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int p[101];
int dp[101][101][101][2];
bool check[101];

void test()
{
	int n;
	cin >> n;

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++)
				dp[i][j][k][0] = dp[i][j][k][1] = INF;

	for (int i = 1; i <= n; i++)
	{
		cin >> p[i];
		check[p[i]] = true;
	}

	int even = 0, odd = 0;
	for (int i = 1; i <= n; i++)
	{
		if (check[i]) continue;
		if (i % 2) odd++;
		else even++;
	}

	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= even; j++)
		{
			for (int k = 0; k <= odd; k++)
			{
				if (p[i])
				{
					if (p[i] % 2)
						dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
					else
						dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1);
				}
				else
				{
					if (j - 1 >= 0)
						dp[i][j][k][0] = min(dp[i - 1][j - 1][k][0], dp[i - 1][j - 1][k][1] + 1);
					if (k - 1 >= 0)
						dp[i][j][k][1] = min(dp[i - 1][j][k - 1][0] + 1, dp[i - 1][j][k - 1][1]);
				}
			}
		}
	}
	cout << min(dp[n][even][odd][0], dp[n][even][odd][1]);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	test();

	return 0;
}