uva 10271 Chopsticks(dp)

时间:2021-12-26 23:13:30

题目连接: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;
}