original title link:

Http://acm.hdu.edu.cn/showproblem.php? Pid=1421

?

1: original title content

= 9. now, poor xhd wants to know what's best after moving through the 2*k item (that is, minimal fatigue). Please tell him,.

2 1

1 3

4

Two: analysis, understanding,

first of all, how do you move? How do you get each pair? If there are four ABCD numbers, and a

(a-b) ^2+ (C-D) ^2 < (A-C) ^2+ (B-D) ^2

(a-b) ^2+ (C-D) ^2 < (A-D) ^2+ (B-C) ^2

That is, each pair of items should be the closest thing to weight. That is to say, each item should be a continuous.

after sorting the n items

The array dp[n][k] represents the optimum state of the K pair in the N object, and the decision to achieve this state might be:

Item n is not moving, that is, moving K pairs in the front n - 1 items, then the fatigue value is still dp[n - 1][k];

The first n items to move, then according to the above, the N - 1 items should also move, i.e. the N - 2 items to move K - 1 of the items, and then moved to the last item, then the fatigue value of dp[n - 2][k - 1] (a[n - 1]-a[n]) (* a[n - 1]-a[n], N - 1) because of the number of the total number of items is less than 1.

Three: AC code

#include

#include

#include

#include

Using namespace std;

Const int INF = 1 < < 30; / / idiot, the maximum int value is 2^31-1, not 2^31, I go oh

Int a[2005];

Int dp[2005][1005];

Int, main ()

{

Int, N, k;

While (~scanf ("%d%d", "&n", "&k"))

{

For (int i = 1; I < n; i++)

Scanf ("%d", &a[i]);

Sort (a + 1, a + N + 1);

For (int j = 1; J < K; j++)

{

For (int i = 1; I < n; i++)

{

If (J * 2 < = I)

Dp[i][j] = min (dp[i - 1][j], dp[i - 2][j - 1] + (a[i - 1] - a[i]) * (a[i - 1] - a[i]));

Else

Dp[i][j] = INF;

}

}

Printf ("%dn", dp[n][k]);

}

Return 0;

}