Nigga's blog

Spoj DP problem
By Nigga, 12 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ... :(

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 .

→ Reply