darkworld1's blog

dp on string :)
By darkworld1, history, 7 years ago, In English

Hello , i got stuck with the problem of dp where , i was not able to build dp state ? Link of the problem is https://atcoder.jp/contests/abc122/tasks/abc122_d

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Keep the position and last three letters in the dp state. For each new letter, check if old three letters + new letter doesn't violate the rules. Then you can calculate the dp easily. I would prefer to implement recursively as it looks like a dfs.

→ Reply