I'm trying to find an algorithm for calculating Minimum Insertion needed to make a string palindrome. My Idea is to find the length of longest palindromic sub sequence for the given string and subtract it from the string length. Will it work? Or there is any cornered case where it will not work, Please help !!!!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:10:43
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:10:43
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.11.2024 22:24:19 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Let dp[l][r] be the minimum number of insertions to make s[l...r] a palindrome.
If s[l] = s[r], then obviously dp[l][r] = dp[l + 1][r - 1].
Otherwise, you must either add s[r] to the beginning or s[l] to the end so dp[l][r] = 1 + min(dp[l + 1][r], dp[l][r - 1]).
Hi Petar, Thank you very much for your Idea. That's really good. :)
But can you please tell me if there is any pitfall for my approach, thank you in advance :)
I don't know, perhaps you can try submitting it on SPOJ (http://www.spoj.com/problems/IOIPALIN/). If it doesn't get accepted, then implementing my approach and stresstesting it against yours should easily produce a counter-example
Thank You :)
Accepted... :D I think my Idea is OK...
Thank you very much for that nice problem ....