Optimizing n^3 DP
Разница между en4 и en5, 15 символ(ов) изменены
Problem Statement:↵
There exists a single player game called "Pair of Fours". In this game, there are four types of cards, labeled 'U', 'B', 'O' and 'N'. There are N cards in total, and initially they are arranged so that no adjacent cards are of the same type. The game goes as follows:↵

1. The player chooses a card and removes it. This means the cards on the left and the right are now adjacent.↵
2. While the (now adjacent) left and right cards are of the same type, remove both cards and add one to the score.↵
3. If there are no cards left, the game ends. Otherwise, go back to step one.↵

Sample case:↵

13<br>↵
N U B O B U O N B O N U O ↵

I came up with an O(n^3) DP solution, but since n <= 1000, it definitely gets TLE verdict:↵

`dp[i][j] = max(dp[i][k]+dp[k+1][j], dp[i+1][j-1]+
1(a[i] == a[j]))`↵

Is there a way to optimize this, or is DP not the correct train of thought?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский szawinis 2017-03-22 18:52:39 15 Tiny change: 'i+1][j-1]+1)`\n\nIs t' -> 'i+1][j-1]+(a[i] == a[j]))`\n\nIs t'
en4 Английский szawinis 2017-03-22 18:15:44 10 Tiny change: 'otal, and they are ' -> 'otal, and initially they are ' (published)
en3 Английский szawinis 2017-03-22 18:15:03 92
en2 Английский szawinis 2017-03-22 18:13:55 4 Tiny change: 'ase:\n\n13\nN U B O ' -> 'ase:\n\n13<br>\nN U B O '
en1 Английский szawinis 2017-03-22 18:13:36 922 Initial revision (saved to drafts)