Повідомлень: 43 Звідки: school Зареєстрований: 29.12.07
Опубліковано 31-10-2008 14:39
Всім привіт...
Ось "зустрівся" на тімусі з задачею 1635, яка мене вже...
Хотілось б її тут розібрати (звісно якшо ніхто не проти!)
І так, я написав динаміку - при найгіршому тесті О(N^3).
Зрощуміло, що по часу не пройде в ніякі ворота
Потім я трохи оптимізував прогу, але все рівно при найгіршому тесті О(N^3)
Опишу свою динаміку
Нехай a[i,j] - мінімальна кількість паліндромів на яку можна розбити рядок від i-го до j-го символа
Тоді, зрозуміло:
1. Якщо i>j то a[i,j]=0
2. a[i,j]=1 - якщо рядок (від i до j) паліндром
3. a[i,j]=мінімальному числу з (a[i,p]+a[p+1,j]) де p = i..(j-1)
Ось і все!
Зробив я оптимізацію для пошуку паліндрома(перевіряю за О(1)) і...все!
Таким чином я отримую ТЛЕ 32
Я вважаю, що потрібно якось оптимізувати цю динаміку, але на жаль поки що не знаю як саме...Або ж я помиляюся і тут зовсім інший розв"язок...
Будь ласка покажіть на помилку ?
Чи на правильному я шляху ?
Ти на правильному шляху, тільки додай мінімальну оптимізацію: a[i,j]=min(a[i,j-k]+1), для всіх k, при яких підстрічка з j-k-о по j-ий символ є паліндромом. (Принаймні я так рішав, думаю є і кращі розвязки).
Ну ше треба помітити, що тобі абсолютно не потрібно тримати двовимірний масив для результатів. Тобто: ти маєш один масив двовимірний, a[i,j] - який означає чи підстрічка з i до j є паліндромом чи ні. А інший масив - одновимірний - буде тримати таку інформацію: res[i] - результат для підстрічки з 1-о по i-ий символ. Тоді складність буде O(n^2), для формування першого масиву і O(n^2) для формування другого масиву. Отже отримали алгоритм який за квадрат рішає задачу.
Birthday(s):
