ZOJ 2068 Chopsticks

Description

It's December 2nd, Mr.L's birthday! He invited K people to join his birthday party, and would like to introduce his way of using chopsticks. So, he should prepare K+8 sets of chopsticks(for himself, his wife, his little son, little daughter, his mother, father, mother-in-law, father-in-law, and K other guests). But Mr.L suddenly discovered that his chopsticks are of quite different lengths! He should find a way of composing the K+8 sets, so that the total badness of all the sets is minimized.

Input

The first line in the input contains a single integer T, indicating the number of test cases(1<=T<=20). Each test case begins with two integers K, N(0<=K<=1000, 3K+24<=N<=5000), the number of guests and the number of chopsticks. There are N positive integers Li on the next line in non-decreasing order indicating the lengths of the chopsticks.(1<=Li<=32000).

Output

For each test case in the input, print a line containing the minimal total badness of all the sets.

Sample Input

1
1 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98 103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164

Sample Output

23

Note

For the sample input, a possible collection of the 9 sets is:

8,10,16; 19,22,27; 61,63,75; 71,72,88; 81,81,84; 96,98,103; 128,129,148; 134,134,139; 157,157,160

动规，首先可以证明A，B一定是连续的，然后只要对筷子的长度排序，从大到小处理，保证C的存在即可.

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<functional>
using namespace std;
const int maxn = 5005;
int T, K, n, a[maxn], f[maxn][1005];

int cmp(const int &a, const int &b)
{
  return a > b;
}

int p(int x, int y)
{
  return (a[x] - a[y])*(a[x] - a[y]);
}

int main()
{
  cin >> T;
  while (T--)
  {
    cin >> K >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, cmp);
    memset(f, 1, sizeof(f));    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
      for (int j = min(K + 8, i / 3); j >= 0; j--)
      {
        f[i][j] = f[i - 1][j];
        if (i >= j + j + j)
          f[i][j] = min(f[i][j], f[i - 2][j - 1] + p(i, i - 1));
      }
    cout << f[n][K + 8] << endl;
  }
  return 0;
}