axdxtxdy's blog

By axdxtxdy, history, 6 weeks ago, In English

Given n numbers (n is even), you have to perform n/2 operation from 1 to n,

in ith operation choose any two elements from the given array and add i*gcd(x,y) to your score and then remove both the elements from the array.

You have to maximize the final score.

2 <= N <= 20

1 <= Ai <= 10^9

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by axdxtxdy (previous revision, new revision, compare).

»
6 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it
for mask in range(3, 1 << n):
  if builtin_popcount(mask) % 2 == 1:
     continue
  for j in range(0, n):
    for k in range(j+1, n):
      if (1 << k) & mask and (1 << j) & mask:
        dp(mask) = max(dp(mask), dp(mask ^(1 << j) ^ (1 << k)) + ( ((builtin_popcount(mask)) / 2)) * gcd(a(k), a(j)) 

I don’t if this works but this is pseudo code what I would write in contest if i see this problem