一 题意描述：
就是在n支筷子里面选取k+8双筷子，每双筷子有三支，其中两支（A，B）比较小，第三支C比较大。下面我们要使k+8双筷子中(A-B)^2之和最小。应当怎样选取？
二 思路分析：
我们可以用：dp[i][j]表示从前j个筷子里面选取i双（先只取两只筷子组成一双）筷子时(A-B)^2的最小值。
那么对于第j支筷子而言：
我们有dp[i][j]=min{dp[i][j-1],dp[i-1][j-2]+(f[j]-f[j-1])*(f[j]-f[j-1]) | (n-j)>3*(k+8-i) }.其中dp[i][j-1]表示不拿第j支筷子，在第j-1支筷子里面就已经选好了i双筷子。dp[i-1][j-2]表示拿了第j支筷子,那么我们可以想到第j-1只筷子肯定被拿了，而且是和第j支筷子组成一双，那么我们可以推断出在前j-2支筷子里面我们只组成i-1双筷子，即dp[i-1][j-2].
三 AC代码：
1 #include<iostream> 2 # include<cstring> 3 # include<cstdio> 4 using namespace std; 5 long MAX = 2147483647; 6 int dp[1010][5005]; 7 int f[5005]; 8 int main() 9 { 10 int t; 11 cin>>t; 12 while(t--) 13 { 14 int k,n; 15 cin>>k>>n; 16 for(int i=1;i<=n;i++) 17 cin>>f[i]; 18 memset(dp,0,sizeof(dp)); 19 k+=8; 20 long temp; 21 for(int i=1;i<=k;i++) 22 { 23 for(int j=2*i;j<=n;j++) 24 { 25 dp[i][j]=MAX; 26 if(j>2*i) dp[i][j]=dp[i][j-1];//j>2*i表示第j个没选 27 if(n-j>(k-i)*3) 28 temp=dp[i-1][j-2]+(f[j]-f[j-1])*(f[j]-f[j-1]); 29 if(temp<dp[i][j]) dp[i][j]=temp; 30 } 31 } 32 cout<<dp[k][n]<<endl; 33 } 34 return 0; 35 }