fork download
copy 
  1. dp_left=[]
  2. dp_right=[]
  3. dp_right_idx=[]
  4. n=int(input())
  5. row=[]
  6. row=input().split()
  7.  
  8. for i in range(n):
  9.     row[i]=int(row[i])
  10.  
  11. row=sorted(row)
  12.  
  13. for i in range(1<<n):
  14.     dp_right.append(1000000000000)
  15.     dp_right_idx.append(-1)
  16.     for j in range(n):
  17.         if i & (1<<j):
  18.             if row[j]<dp_right[i]:
  19.                 dp_right[i]=row[j]
  20.                 dp_right_idx[i]=j
  21. #    print(dp_right_idx[i],end=" ")
  22.  
  23. #print()
  24.  
  25. dp_right[0]=0
  26. dp_left.append(0) #dp_left[0]=0
  27. for i in range(1,1<<n):
  28.     dp_left.append(10000000000000)
  29. for i in range(1,1<<n):
  30.     for j in range(n):
  31.         for k in range(j+1,n):
  32.             if ((i>>j)&1) and ((i>>k)&1):
  33.                 val=max(row[j],row[k])
  34.                 LEFT=i^(1<<j)^(1<<k)
  35.                 if LEFT!=0:
  36.                     val=val+dp_right[(1<<n)-1-LEFT]+dp_left[LEFT^(1<<dp_right_idx[(1<<n)-1-LEFT])]
  37.                 dp_left[i]=min(dp_left[i],val)
  38.     if dp_left[i]==10000000000000:
  39.         for j in range(n):
  40.             if (i>>j)&1:
  41.                 dp_left[i]=row[j]
  42. #    print(dp_left[i],end=" ")
  43.  
  44. print(dp_left[(2**n) -1])
  45.  
Success #stdin #stdout 0.02s 28376KB
comments (?)
stdin
copy 
5
23 22 2 18 6
stdout
copy 
63
https://ideone.com/Dqjupr
language:
Python 3 nbc (python 3.7.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!