Please help in a possible DP problem .

Правка en1, от helloworld1102, 2021-10-05 21:05:16

Hello, Hi there , if anyone know the below problem solution please tell. I thought this problem using binary search , greedy, but no use. So finally i think it will be possible by DP. (but not getting possible states and transitions). If anyone helps, that would be very nice of you. So the problem goes like this -->

A bus stops at n bus stops, each bus stop having a[i] people. The bus needs to take in all the people on the bus. People from 1 bus stop get down before the next bus stop arrives. They use a resizing tech which allows the bus to be resized to whatever capacity they want. This action can be done only b times at max. The uselessness of the bus is the summation of a total number of unoccupied seats across n stops. Find the minimum uselessness the bus can achieve if the resizing tech is used optimally.

1<=a[i]<=10^6, 1<=b<=n<=400

Ex 1: a = [10 20] b = 0 Ans:10 Explanation – the resizing tech cannot be applied. hence the capacity of the bus is 20 initially. in the first stop, 20-10 seats were unused. in the second stop 20 – 20 seats are unused. Total unused seats = 10

Ex 2: a = [10 20 30] b = 1 Ans: 10 Explanation – the resizing tech can be applied only once. The capacity of the bus is 10 initially. In the first stop 10-10 seats unused = 0. in the second stop, the tech is used to resize to 30. 30 – 20 seats unused.

In the third stop, 30-30 seats unused

Total unused seats = 10.

If anyone know how to do it, please explain .

THANK YOU.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский helloworld1102 2021-10-05 21:05:16 1537 Initial revision (published)