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. for i in range(1<<n):
  12.     dp_right.append(1000000000000)
  13.     dp_right_idx.append(-1)
  14.     for j in range(n):
  15.         if i & (1<<j):
  16.             if row[j]<dp_right[i]:
  17.                 dp_right[i]=row[j]
  18.                 dp_right_idx[i]=j
  19.     #print(dp_right_idx[i],end=" ")
  20.  
  21. #print()
  22.  
  23. dp_right[0]=0
  24. dp_left.append(0) #dp_left[0]=0
  25. for i in range(1,1<<n):
  26.     dp_left.append(10000000000000)
  27. for i in range(1,1<<n):
  28.     for j in range(n):
  29.         for k in range(j+1,n):
  30.             if ((i>>j)&1) and ((i>>k)&1):
  31.                 val=max(row[j],row[k])
  32.                 LEFT=i^(1<<j)^(1<<k)
  33.                 if LEFT!=0:
  34.                     val=val+dp_right[(1<<n)-1-LEFT]+dp_left[LEFT^(1<<dp_right_idx[(1<<n)-1-LEFT])]
  35.                 dp_left[i]=min(dp_left[i],val)
  36.     if dp_left[i]==10000000000000:
  37.         for j in range(n):
  38.             if (i>>j)&1:
  39.                 dp_left[i]=row[j]
  40.     #print(dp_left[i],end=" ")
  41.  
  42. print(dp_left[(2**n) -1])
Success #stdin #stdout 0.02s 27704KB
comments (?)
stdin
copy 
4
1 2 5 8
stdout
copy 
15
https://ideone.com/EXBMqA
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!