思路：先排序。
dp[i][j]表示前i件物品选j对的最优解。状态转移方程：
如果 i == j*2，只有一种选择，dp[i][j] = dp[i-2][j-1] + (a[i]-a[i-1])*(a[i]-a[i-1])
否则 dp[i][j] = min( dp[i-2][j-1] + (a[i]-a[i-1])*(a[i]-a[i-1]) ，dp[i-1][j]).
#include#include #include using namespace std; int dp[2010][1010]; int main() { int n,k,a[2010]; while(~scanf(%d %d,&n,&k)) { for(int i = 1; i <= n; i++) scanf(%d,&a[i]); sort(a+1,a+1+n); memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= i/2; j++) { if(i%2 == 0 && j == i/2) dp[i][j] = dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]); else dp[i][j] = min(dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]), dp[i-1][j]); } } printf(%d ,dp[n][k]); } return 0; }