Блог пользователя legar

Help in this interesting dp Problem
Автор legar, история, 9 лет назад, По-английски

You are given a list L of N integers. < 1000 Let's define an operation of cutting the list as follows: Suppose L = {l1, l2, ..., li, li+1, ..., lN}, then, cutting the list L at index i will split L into two nonempty sub-lists L1= {l1, l2, ...; li} and L2= {li+1, li+2, ..., lN}. Now, for each of sub-list Li, we can find the difference between the maximum value (Mi) and minimum value (mi) of Li and call it di. The task is to cut the list into K sub-list (1 ≤ K ≤ N) so that ans = d1+d2+....+dk, is minimized. Print ans. (1 ≤ K ≤ N ≤ 1000). The O(N*N*K) solution is very slow. Thanks.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Link to the question ?

→ Ответить
»
9 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

In your problem it is clear that the brute force solution is dp[i][j] = the total minimal cost for the first i elements to split them in j sub-lists, and for that you fix the left side of your last list. O(n*n*k) There is an optimization that can transform you solution in O(n*k* logn ) , noticing than for your dimension j , once we iterate through all i s , the optimal left side for dp(i,j) is >= or <= then the left side for dp(i-1,j) . You can do a divide and conquer algorithm for all possible values of j. Last Edit : This solution doesn't work, you can brute force the left sides and the propery isn't satisfied :(

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know a solution in O(n*k) where the cost of list is maximum or minimum and it implies deque and dynamic, but combining those two does not sound good.Did you come up with this problem or it is from some archive/contest?(If you thought of it,there may be no faster solution than O(n*n*k)).

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This problem is from ACM-ICPC Thailand Southern Programming Contest 2012, I can't give you link to the problem because de OJ is no free for all people, but the O(n*n*k) solution is TLE.

    → Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

This is the problemset for the contest that contains this problem (2012):D

Problem Link

I think you misunderstand the problem, the correct constraints are: 1 ≤ K ≤ N ≤ 400

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think I have the solution. Multiply the array by -1 to transform the problem to calculate the maximum sum that can be obtained by adding or subtracting 2*k elements from the array, with the rule that in the pair of selected elements 2*i + 1 and 2*i + 2 (0 <= i < k), there is exactly one summed and one subtracted from the sum total. This new problem can be solved with a DP in O (N * K).

→ Ответить