Need help with the program which was on my last programming competition

[Matep]

Hi guys, need help with the idea on how to solve this assigment with an fast enough algorithm.

There is a parkinlot with P spaces, parked one next to the other in one line. '#' is spot where the car is parked and '.' is a free spot. then K big trucks come and each of them takes L spaces and if there is no room you need to remove some of the cars. The task is to write an algorithm fast enough (under 1 sec) which will find the least number of cars needed to be removed so all the trucks could fit (trucks dont need to be one next to each oder)

entry
P-size of the parking lot
K-number of big trucks
L-length of the truck
(P,K,L <=1000)

exit
number of cars needed to be removed

test examples

1.entry
6 1 3
#.#.##

1.exit
1

2.entry
9 2 3
.##..#..#

2.exit
2

3.entry
15 2 5
.#.....#.#####.

3.exit
3


All help is appriciated!

[ne555]

found a O(P*K) solution, considering the limits of the problem think that it is good enough.
First, compute the cost of trying to place a truck in every spot O(P)

The problem is now to chose K elements that are separated by at least L cells, and whose sum is minimal.
Then you generalise. you'll compute the minimum sum in the sub-array [0; x] (where x can go from 0 to P-1) with 1, 2, ..., K elements. Notice that when adding an element you can use the previous results.

[Matep]

Ty @np555
I think i understand what you're saying, ill try to write it down and if it doesn't exceed the time limit i will be very happy haha if not we'll talk again..