UVA 10271 Chopsticks 筷子 DP - c++编程基础

题意：给出n只筷子的长度，在其中取k+8组，每组筷子有三根，两根短的一根长的，求各组短筷子长度差的最小的平方和。

其实是njupt 1581升级版（题解），不过这次还附加了个长筷子，所以那题的转移公式得改一下。

由于njupt 1581这题的做法是从小到大排序考虑第i只筷子看是否要取，但是这题还需要的是俩短筷子的，所以第i个肯定不能考虑（因为在前i个中找不到能和它搭配的更长的筷子）。

所以我们只要从大到小排序来考虑就可以了，思路和1581一模一样。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        uva10271.cpp 
*  Create Date: 2013-11-13 00:56:45 
*  Descripton:  dp  
*/  
  
#include   
#include 




  
  
#define min(a, b) ((a) < (b)   (a) : (b))  
#define sqr(a) ((a) * (a))  
  
int dp[5010][1010];  
int a[5010], n, k, t;  
  
int main() {  
    scanf("%d", &t);  
    while (t--) {  
        scanf("%d%d", &k, &n);  
        k += 8;  
  
        for (int i = n; i >= 1; i--)  
            scanf("%d", &a[i]);  
          
        for (int i = 1; i <= n; i++)  
            for (int j = 1; j <= k; j++)  
                dp[i][j] = 0x7ffffff;  
  
        for (int i = 3; i <= n; i++)  
            for (int j = 1; j <= k; j++)  
                if (i >= j * 3)  
                    dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + sqr(a[i - 1] - a[i]));  
  
        printf("%d\n", dp[n][k]);  
    }  
    return 0;  
}