fork download
copy 
  1. def min_cost(cost, pair_cost, k):
  2.     n = len(cost)
  3.     dp = {}
  4.  
  5.     def solve(i, j, k_used):
  6.         if i > j:
  7.             return 0
  8.         if (i, j, k_used) in dp:
  9.             return dp[(i, j, k_used)]
  10.  
  11.         ans = float('inf')
  12.         # Buy leftmost
  13.         ans = min(ans, cost[i] + solve(i + 1, j, k_used))
  14.         # Buy rightmost
  15.         ans = min(ans, cost[j] + solve(i, j - 1, k_used))
  16.         # Buy leftmost and rightmost
  17.         if k_used < k:
  18.             ans = min(ans, pair_cost + solve(i + 1, j - 1, k_used + 1))
  19.  
  20.         dp[(i, j, k_used)] = ans
  21.         return ans
  22.  
  23.     return solve(0, n - 1, 0)
Success #stdin #stdout 0.09s 14044KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RrRVeH
language:
Python 3 (python  3.12)
created:
1 day ago
visibility:
public

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!