1579.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1579 on 2005-12-05 at 11:03:34 */ 
#include <cstdio>

const int K_MAX = 1024;
const int N_MAX = 5400;
const int INFINITE = 100000000;

int bad[N_MAX][K_MAX];

inline int min(int, int);

int main()
{
	int chop[N_MAX];
	int t, T, i, j;
	int n, k;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &k, &n);
		k += 8;
		for(i = 0; i < n; i++) {
			scanf("%d", &chop[i]);
		}
		bad[n-1][1] = bad[n-2][1] = INFINITE;
		bad[n-1][0] = bad[n-2][0] = 0;
		for(i = n-3; i >= 0; i--) {
			bad[i][0] = 0;
			for(j = 1; j <= k; j++) {
				if(j*3 <= n-i) {
					bad[i][j] = min(bad[i+2][j-1]+(chop[i]-chop[i+1])*(chop[i]-chop[i+1]), 
						bad[i+1][j]);
				} else {
					bad[i][j] = INFINITE;
				}
			}
		}
		printf("%d\n", bad[0][k]);
	}

	return 0;
}

inline int min(int a, int b)
{
	return a < b ? a : b;
}