problem statement: We are given n gold mines having A[i] amount of gold at ith gold mine where 1<=i<=n. All gold mines are located on a straight line , the location of each mine is given by B[i] where 1<=i<=n. Now we want to consolidate all gold into exactly k mines ( by moving gold from remaining n-k mines to nearby mines). The cost of moving amt amount of gold from mine i to mine j is distance between them times the amount of gold moved, i.e, |B[i]-B[j]|*amt where 0<=amt<A[i]. We can choose any k final gold mine locations where we can consolidate gold from other mines. ( However those k final locations must be among original gold mine locations. For example if n = 2, A = (2, 4), B = (0, 4) and k = 1, then we will choose final gold locations as (4). cost of moving gold from location 0 to 4 is 4*2 = 8 . If we choose final locations as (0), the cost would be 4*4 = 16.) Please help me devising an efficient algorithm to compute the minimum cost . Thanks in advance.
Constraints : 1<=n<=5000,
1<=k<=n,
A[i] is non negative.