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

Spoj DP problem
Автор Nigga, 12 лет назад, По-английски

Can someone help me with this problem http://www.spoj.pl/problems/HIST2 ?

I know how to solve the maximum perimeter, but how can I count the number of permutations?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

Look at the constraints. N <= 15 is shouting bitmasks.

Generally speaking, if a state S can be reached from the states A1,A2,A3....AK, and the function G(state) is the number of ways to generate the state. We have that:

G(S) = G(A1)+G(A2)+G(A3)....+G(AK)

Hope it helps.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You mean to do a function to calculate maximum and another one that count the permutations?

    I try to code that problem ... here's my code ... http://pastebin.com/MKUZA75W ... but it doesn't count properly the permutations ... :(

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I am getting TLE in this question . Did you solve it ? I used dp+ bitmask . Here is the link for code : http://ideone.com/vnLa8S Can you tell how to optimise it .

→ Ответить