Home » C++ » Hdu1421 --DP moved to the bedroom

Hdu1421 --DP moved to the bedroom

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

1: original title content

Problem Description
moved to the bedroom is very tired, xhd deep. The time back in July 9, 2006, xhd was forced to move from building 27, building 3, No. 10, because to seal floor. N items at the bedroom, xhd began in a daze, because n is a whole number less than 2000, too much, so xhd decided to throw up 2*k over the line. But it will be very tired, because 2*k is not small is an integer not greater than n. Fortunately, xhd based on years of experience to move things found every move a fatigue is the left and right hand items the weight difference (which is proportional to the Square in a xhd, each move two things left a right one). For example, xhd left for the weight of 3 items, right hand holding the weight of 6 items, he moved the fatigue degree of (6-3) ^2
= 9. now, poor xhd wants to know what's best after moving through the 2*k item (that is, minimal fatigue). Please tell him,.


each group has two lines of input data. The first line has two numbers n, K (2<=2*k<=n<2000). The second line has n integers representing the weight of the n item (the weight is a positive integer less than 2^15).


corresponds to each set of input data, and only one output represents his minimum fatigue, each line.

Sample Input

2 1
1 3

Sample Output


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

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]));
Dp[i][j] = INF;
Printf ("%dn", dp[n][k]);
Return 0;