uva 10271 Chopsticks(dp)

题目连接：10271 - Chopsticks

题目大意：给出m和n, 然后给出n根筷子从小到大给出， 现在要从这n根筷子中选出m + 8组筷子， 每组筷子包括三根， 现在要求所有m + 8组每组筷子中最短两根筷子之差的平方  的和最小，输出最小值。

解题思路：一开始想用贪心做， 后来发现子问题是互相干预的。

dp[i][j]表示在在第i根筷子已经取了j组筷子后的和的最小值， 因为给出的筷子已经从小到大排列， 所以每根筷子的最小组合肯定是和前后的筷子，这样遍历的时候其实可以不用想太多，直接每个和后面一个配对考虑就好了。然后对于第i根筷子是取还是不取除了和最小的条件之外还有要求取了i和i + 1这两根筷子之后， 还能保证前面确定的j对筷子都能满足再添加一根较长的（题目要求三根）。

#include <stdio.h>

#include <string.h>

const int N = 5010;

const int MAX = 0x3f3f3f3f;

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

int val[N], dp[N][1010];

int P(int a) {

    return a * a;

}

int main () {

    int cas, n, m;

    scanf("%d", &cas);

    while (cas--) {

	scanf("%d%d", &m, &n);

	memset(dp, MAX, sizeof(dp));

	m += 8;

	dp[0][0] = 0;

	for (int i = 1; i <= n; i++) {

	    scanf("%d", &val[i]);

	    dp[i][0] = 0;

	}

	for (int i = n - 2; i >= 1; i--) {

	    for (int j = m; j >= 1; j--) {

		dp[i][j] = dp[i + 1][j];

		if (dp[i + 2][j - 1] != MAX && n - i - j * 3 >= -1)

		    dp[i][j] = min(dp[i][j], dp[i + 2][j - 1] + P(val[i] - val[i + 1]));

	    }

	}

	printf("%d\n", dp[1][m]);

    }

    return 0;

}