Hi, I can't solve it for a long time. There are really short codes, but I can't get the main idea :( Thanks for help.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.05.2024 12:14:58 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Ok Let's notice a fact That f(a1, a2, ..., an) = |a1| — f(a1, a2) + |a2| — f(a2, a3) .... + |ai| — f(ai, a[i+1) + ... + |an|
Now just solve it n ^ 2 and after that solve it nk
How?
dp[i] = lets partition it till i-1
for (int l = 0; l < n; ++l)
for (int r = 1; r <= n; ++r)
dp[r] = min(dp[r], dp[l] — (r != n? lcp(a[l], a[r]): 0) + |a[l]| + |a[l + 1]| + ... + |a[r — 1]| — f(a[l], a[l + 1]) — f(a[l+1], a[l+2]).... f(a[r — 2], a[r — 1) (this can be found with partial sum));
I can't understand :(
well if you partition the sequence into two subsequences the sequence will be like this
c means it belongs to subsequence c
b means it belongs to subsequence b
bbbcccbbccbbbb
in those fors dp[r] = the best way to partition it till r which r and r — 1 are different and dp[n] is a special case where the nth element doesnt exist
in those 2 fors l means the first place before r where l and l — 1 are different
the things that will be added are -f(l, l + 1) -f(l + 1, l + 2) ... -f(r — 2, r — 1) and the sizes of the elements by that lcp i mean (l != 0? |f(a[l-1], a[r])|: 0)
if you didn't understand tell me again ;D it will be appreciated if you tell the place which you can't understand too
Actually I can't understand anything, there is some formulas and something but what can I do with them? :D
http://codeforces.com/blog/entry/1976
It's a decent explanation even with Google Translate.
I read it but I can't understand with translate.
First, some notation. We have binary strings s1... sn each of length k. Let si(l) denote the prefix of si of length l.
Now, let dp[x][suf] be the minimum cost for strings s1... sx given that one subsequence ends in sx and the other ends in suf. Note that suf can have length between 0 and k. Our state transition is:
Here is the logic behind the transition. In order to make two subsequences, one ending with sx and the other in suf, we can either append sx to the subsequence ending with sx - 1, or we can append sx to a subsequence ending in sx(l) where 0 ≤ l ≤ k. In the later case, we will end up with one subsequence ending with sx and the other subsequence ending with sx - 1, so we need only evaluate this case if sx - 1 ends in suf.
I'll let you figure out the details of the implementation as an exercise. You'll need to figure out how to handle state transitions in an efficient manner.
I solved it yesterday, but I really appreciated for your help. Thanks.