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.
Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.07.2024 20:21:15 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Link to the question ?
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 :(
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)).
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.
If you find the solution please let us know
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 ≤ 400Yes, but number of cases is 120.
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).