1234.cpp

acm.zju.edu.cn第1234题（动态规划）

#include <algorithm>
#include <memory>
#include <iostream>
using namespace std;
int table[5005][1005];
const int INFI = 9999999;

int main()
{
	int t, k , n, chopsticks[5001];

	cin >> t;
	while(t--)
	{
		cin >> k >> n;
		memset(table, INFI, sizeof(table));
		for(int i = 1; i <= n; i++)
			cin >> chopsticks[i];
		for(int i = 1; i <= n; i++)
			table[i][0] = 0;
		
		for(int i = 1; i <= k + 8; i++)
			for(int j = n - 2; j >= 1; j--)   // 从倒数第j个筷子开始取i * 3只筷子供i个人使用
				if(n - j + 1 < i * 3)   // 取不了
					continue;
				else
					table[j][i] = min(table[j + 1][i], 
					   (chopsticks[j+1]-chopsticks[j])*(chopsticks[j+1]-chopsticks[j]) + table[j + 2][i - 1]);
	  	  cout << table[1][k + 8] << endl;
	}
	return 0;
}