UVa Problem 10271 젓가락 (젓가락)

// Chopsticks （  ）
// PC/UVa IDs: 111107/10271, Popularity: B, Success rate: average Level: 3
// Verdict: Accepted
// Submission Date: 2011-10-18
// UVa Run Time: 0.100s
//
//     （C）2011，  。metaphysis # yeah dot net
//
// [    ]
//   badness[i][j]     j        i                ，length[j]   
// j       ，          ：
//
// badness[i][j] = min{badness[i][j - 1], badness[i - 1][j - 2] + (length[j] -
// length[j - 1]) * (length[j] - length[j - 1) | j >= 3 * i - 1}
//
//            （     ）：
//
// ...，C1，C2，C3，...
//
//     ，  C1 < C2，        C1         ，  C2           。   
//      。        C1    C2       ，    C1   C2           C1
//                 ，        。              ，      
//       ，          。

#include <iostream>

using namespace std;

#define MAXN 5001

int length[MAXN];
int badness[MAXN];
int difference[MAXN];
int nGuests, nChopsticks;

//             。
int dynamic_programming()
{
	for (int i = 0; i <= nChopsticks; i++)
		badness[i] = 0;

	for (int i = 1; i <= nGuests; i++)
	{
		int setted = nChopsticks - 3 * (nGuests - i);
		for (int j = setted - 1; j >= 2 * i; j--)
			badness[j] = badness[j - 2] + difference[j];
			
		for (int j = 2 * i + 1; j <= setted - 1; j++)
			badness[j] = min(badness[j], badness[j - 1]);

		badness[setted] = badness[setted - 1];
	}
	
	cout << badness[nChopsticks] << endl;
}

int main(int ac, char *av[])
{
	int cases;
	
	cin >> cases;
	while (cases--)
	{
		cin >> nGuests >> nChopsticks;
		nGuests += 8;

		for (int i = 1; i <= nChopsticks; i++)
		{
			cin >> length[i];
			difference[i] = length[i] - length[i - 1];
			difference[i] *= difference[i];
		}

		dynamic_programming();
	}
}