Блог пользователя sparshgunner12

Codeforces Gym — ICPC Season 1 Ep 2(Those planning to give please ignore).
Автор sparshgunner12, 11 лет назад, По-английски

I sat in the gym contest http://mirror.codeforces.com/gym/100228 .Well I am trying to come up with a solution for B)Decorations C)EKG Sequence with no success.Can someone please suggest the algorithm behind these two problems.Seems a lot of u(Over 100 teams) have solved it.Thanks in advance.

Теги gym
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B:
make a graph with M vertices and there is an edge from i to j if and only if you can use bead[j] immediately after bead[i] — in other word last L-1 characters of bead[i] and first L-1 characters of bead[j] is same .
Answer is number of paths with length of L in this graph .
to find this value , use dynamic programming with this state : index of current node and remaining length of path .

→ Ответить