Chopsticks/문보창

소감

2006-01-04 Accepted 1.123 500

가장 큰 젓가락 세트부터 선택한다고 보았을 때, 총 K + 8 번의 선택이 존재하고, 다음 점화식이 나올 수 있다.

D[a]n-3a+2 ~ (k+9-a)*2 = (L(i) - L(i-1))^2 + mini+2<=k{ D[a-1][k] }

각 선택마다 선택할 수 있는 젓가락의 범위를 지정하는 것을 통해, 3개의 젓가락중 가장 큰 젓가락은 신경쓰지 않아도 된다. 위에서 a 는 각 선택, n 은 젓가락 수, k 는 사람 수. 여기서

mini+2<=k{ D[a-1][k] }

은 앞의 계산 결과를 이용하여 O(1) 시간만에 계산 할 수 있고, a 는 K + 8 번 있으므로 O(kn) 복잡도가 걸린다.

코드

// 10271 - Chopsticks
#include <iostream>
using namespace std;

#define MAX_NUM 1000000000
#define MAX_STICK 5003

static int nPerson, nStick;			// 손님수, 젓가락 수
static int stick[MAX_STICK+1];		// 젓가락
static int d[2][MAX_STICK+1];		// 다이나믹 테이블

inline int calcDegree(int i)
{
	int x = stick[i] - stick[i-1];
	return x * x;
}

inline int findMin(int k, int x, int n)
{
	int min = d[k][x];
	for (int i = x + 1; i <= n; i++)
		if (min > d[k][i])
			min = d[k][i];
	return min;
}

void input()
{
	cin >> nPerson >> nStick;
	for (int i = 1; i <= nStick; i++)
		cin >> stick[i];
}

void initTable()
{
	for (int i = nStick - 1; i >= (nPerson + 8) * 2; i--)
		d[1][i] = calcDegree(i);
	d[1][nStick] = MAX_NUM;
}

void process()
{
	int i, min;
	initTable();
	for (int seti = 2; seti <= nPerson + 8; seti++)
	{
		i = nStick - 3 * seti + 2;
		min = findMin(!(seti&0x1), i+2, nStick - 3 * seti + 5);
		d[seti&0x1][i] = calcDegree(i) + min;
		for (i = i-1; i >= (nPerson + 9 - seti) * 2; i--)
		{
			if (min > d[!(seti&0x1)][i+2])
				min = d[!(seti&0x1)][i+2];
			d[seti&0x1][i] = calcDegree(i) + min;
		}
	}
	cout << findMin((nPerson + 8)&0x1, 2, nStick - 3 * nPerson - 22) << endl;
}

int main()
{
	int nCase;
	cin >> nCase;
	for (int i = 0; i < nCase; i++)
	{
		input();
		process();
	}
	return 0;
}

---

Chopsticks