uva 10271 Chopsticks(dp)

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

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

#include   
#include   
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;  
}