Chopsticks UVA - 10271

类似于背包问题的一道动态规划的题目，同时要注意，在选取三根筷子作为结果的时候，要将最小的两根用来计算结果，题目当中给出的数据是从小到大的，所以我们要进行逆序读入，也就是保证读入的数据是从大到小的，这样便于后面动态规划的操作。因为后面动态规划的过程都是两个地选取与前面的某一个进行组合。接着是开始进行动态规划的过程，仿照背包问题的做法和空间优化的方法，因为我们需要的集合个数为K，首先从1开始进行动态规划，假设当前要组合的集合个数为m，每次选取两个点与前面中的某一个点进行组合，同时计算新加入的集合的代价与前m-1个集合代价之和，逐步推进到最后，然后对后续的代价进行更新，保存最小的代价的值即可，具体实现见如下代码：

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<deque>
using namespace std;

class Solve{
public:
	int K, N;
	int value[5010];
	int dp[5010];
	int assit[5010];

	void Init(){
		for (int i = N; i >=1 ; i--)
			cin >> value[i];
		for (int i = 2; i <= N; i++)
			assit[i] = (value[i] - value[i - 1])*(value[i] - value[i - 1]);
	}

	void Deal(){
		Init();
		memset(dp,0,sizeof(dp));
		for (int i = 1; i <= K; i++){
			int amount = 3 * i;
			for (int j = N; j >= amount; j--){
				dp[j] = dp[j - 2] + assit[j];
			}
			for (int j = amount + 1; j <= N; j++)
				if (dp[j - 1] < dp[j]) dp[j] = dp[j - 1];
		}
		cout << dp[N] << endl;
	}
};

int main(){
	int T;
	cin >> T;
	Solve a;
	while (T--){
		cin >> a.K >> a.N;
		a.K += 8;
		a.Deal();
	}
}