Chopsticks/문보창

~cpp
// 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;
}