zoj 1234 Chopsticks

dp[i][k]表示从第i到第n根筷子中，选择k个组合，所得到的权值最小。
故动态转移方程为：
i 从n到1
dp[i][k]=min( dp[i+1][k] , dp[i+2][k-1] + (arr[i+1]-arr[i])*(arr[i+1]-arr[i]) )

我们的主要目的就是使得所选组合的权值最小，而因为这些数据是非递减的，所以说，如果要把第i根筷子加入一个组合的话，那么要使得有i的这个组合最小的话那么和i+1一定符合，也就是i做A,i+1做B，所以(arr[i+1]-arr[i])*(arr[i+1]-arr[i])

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include<algorithm>
using namespace std;

const int maxi = 0x3f3f3f3f;
int dp[5010][1020];
int main() {
	int t, k, n;
	int arr[5001];

	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &k, &n);

		for (int i = 1; i <= n; i++) {
			scanf("%d", &arr[i]);
		}

		for (int i = n; i >= 1; i--) {
			dp[i][0] = 0;
		}

		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= (n - i + 1) / 3; j++) {
				if (j * 3 == n - i + 1) {
					dp[i][j] = dp[i + 2][j - 1] + (arr[i + 1] - arr[i]) * (arr[i + 1] - arr[i]);
				} else {
					dp[i][j] = min(dp[i + 1][j], dp[i + 2][j - 1] + (arr[i + 1] - arr[i]) * (arr[i + 1] - arr[i]));
				}
			}
		}

		printf("%d\n", dp[1][k + 8]);
	}
}