Ada ruang parkir P di tempat parkir, meskipun beberapa ruang ditempati oleh mobil yang diwakili oleh octothorpes #sedangkan ruang bebas adalah titik .. Segera tiba di sana T truk, yang masing-masing akan mengambil ruang tepat L berturut-turut. Truk tidak harus diparkir di sebelah satu sama lain.

Tugas Anda adalah membuat program yang akan menemukan jumlah mobil terkecil yang perlu dilepas untuk memarkir semua truk. Akan selalu ada ruang yang cukup untuk memenuhi semua truk, artinyaT*L<P

Memasukkan

Di baris pertama akan ada tiga bilangan bulat, P, T dan L dipisahkan oleh spasi. Di baris kedua akan ada string karakter P yang mewakili tempat parkir dalam kondisi awal.

Keluaran

Pada baris pertama dan satu-satunya, program Anda harus mencetak jumlah mobil terkecil yang perlu dilepas untuk memarkir semua truk.

Uji kasus

Memasukkan:
6 1 3
#.#.##

Keluaran: 1

Memasukkan:
9 2 3
.##..#..#

Keluaran: 2

Memasukkan:
15 2 5
.#.....#.#####.

Keluaran: 3

Kode terpendek menang. (Catatan: Saya sangat tertarik dengan implementasi pyth, jika memungkinkan)

Python 2, 154 byte

I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]

Pendekatan DP langsung. Sebagian besar program hanya membaca masukan.

Penjelasan

Kami menghitung tabel pemrograman dinamis 2D di mana setiap baris sesuai dengan tempat nparkir pertama , dan setiap kolom sesuai dengan jumlah truk (atau bagian truk) yang ditempatkan sejauh ini. Secara khusus, kolom kberarti bahwa kami telah menempatkan k//Ltruk penuh sejauh ini, dan kami sedang k%Ldalam perjalanan untuk truk baru. Setiap sel kemudian jumlah minimum mobil yang harus dibersihkan untuk mencapai keadaan (n,k), dan keadaan target kami adalah (P, L*T).

Gagasan di balik kekambuhan DP adalah sebagai berikut:

• Jika kita k%L > 0ruang untuk truk baru, maka satu-satunya pilihan kita adalah datang dari k%L-1ruang untuk truk baru
• Kalau tidak, k%L == 0maka kalau kita baru saja menyelesaikan truk baru, atau kita sudah menyelesaikan truk terakhir dan sejak itu melewatkan beberapa tempat parkir. Kami mengambil minimal dua opsi.

Jika k > n, misalnya, kami telah menempatkan lebih banyak kotak truk daripada tempat parkir, maka kami ∞menyatakannya (n,k). Tetapi untuk tujuan bermain golf, kami menempatkan kkarena ini adalah kasus terburuk menghapus setiap mobil, dan juga berfungsi sebagai batas atas.

Ini cukup banyak, jadi mari kita punya contoh, katakan:

5 1 3
..##.

Dua baris terakhir dari tabel adalah

[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

Entri pada indeks 2 dari baris terakhir kedua adalah 2, karena untuk mencapai keadaan 2//3 = 0truk penuh ditempatkan dan menjadi 2%3 = 2ruang bersama untuk truk baru, ini adalah satu-satunya pilihan:

  TT
..XX

Tetapi entri pada indeks 3 dari baris terakhir kedua adalah 1, karena untuk mencapai keadaan 3//3 = 1truk penuh ditempatkan dan menjadi 3%3 = 0ruang bersama untuk truk baru, optimal adalah

TTT
..X#

Entri pada indeks 3 dari baris terakhir melihat dua sel di atas sebagai opsi - apakah kita membawa case di mana kita memiliki 2 ruang untuk truk baru dan menyelesaikannya, atau kita membawa case di mana kita memiliki truk penuh sudah selesai?

  TTT            TTT
..XX.     vs     ..X#.

Jelas yang terakhir lebih baik, jadi kami meletakkan angka 1.

Pyth, 70 byte

JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Pada dasarnya port dari kode di atas. Belum bermain golf dengan baik. Cobalah online

Diperluas

Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Sekarang, jika hanya Pyth yang memiliki banyak penugasan ke> 2 variabel ...

Haskell, 196 karakter

import Data.List
f=filter
m=map
q[_,t,l]=f((>=t).sum.m((`div`l).length).f(>"-").group).sequence.m(:".")
k[a,p]=minimum.m(sum.m fromEnum.zipWith(/=)p)$q(m read$words a)p
main=interact$show.k.lines

Menjalankan semua contoh

& (echo 6 1 3 ; echo "#.#.##" )  | runhaskell 44946-Trucks.hs 
1

& (echo 9 2 3 ; echo ".##..#..#" )  | runhaskell 44946-Trucks.hs 
2

& (echo 15 2 5 ; echo ".#.....#.#####." )  | runhaskell 44946-Trucks.hs 
3

Agak lambat: O (2 ^ P) sedang P adalah ukuran lot.

Mungkin banyak yang tersisa untuk bermain golf di sini.