Python 2, 154 bytes
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]
Un enfoque directo de DP. Una buena parte del programa es solo leer la entrada.
Explicación
Calculamos una tabla de programación dinámica en 2D donde cada fila corresponde a los primeros nlugares de estacionamiento, y cada columna corresponde al número de camiones (o partes de un camión) colocados hasta el momento. En particular, la columna ksignifica que hemos colocado k//Lcamiones completos hasta ahora, y estamos k%Len el camino para un nuevo camión. Cada celda es, entonces, el número mínimo de automóviles para despejar para alcanzar el estado (n,k), y nuestro estado objetivo es (P, L*T).
La idea detrás de la recurrencia de DP es la siguiente:
- Si somos
k%L > 0espacios para un camión nuevo, entonces nuestra única opción es haber sido k%L-1espacios para un camión nuevo
- De lo contrario, si
k%L == 0acabamos de terminar un camión nuevo o si ya habíamos terminado el último camión y desde entonces nos hemos saltado algunos lugares de estacionamiento. Tomamos el mínimo de las dos opciones.
Si k > n, es decir, hemos colocado más plazas de camiones de las que hay plazas de aparcamiento, entonces lo ponemos ∞en estado (n,k). Pero a los efectos del golf, lo ponemos kya que este es el peor caso de eliminación de cada automóvil, y también sirve como límite superior.
Esto fue bastante bocado, así que tengamos un ejemplo, digamos:
5 1 3
..##.
Las dos últimas filas de la tabla son
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]
La entrada en el índice 2 de la segunda última fila es 2, porque para alcanzar un estado de 2//3 = 0camiones llenos colocados y 2%3 = 2espacios para un nuevo camión, esta es la única opción:
TT
..XX
Pero la entrada en el índice 3 de la segunda última fila es 1, porque para alcanzar un estado de 3//3 = 1camiones completos colocados y 3%3 = 0espacios para un nuevo camión, lo óptimo es
TTT
..X#
La entrada en el índice 3 de la última fila considera las dos celdas anteriores como opciones: ¿tomamos el caso donde estamos a 2 espacios para un camión nuevo y lo terminamos, o tomamos el caso donde tenemos un camión lleno? ¿ya terminado?
TTT TTT
..XX. vs ..X#.
Claramente, este último es mejor, así que colocamos un 1.
Pyth, 70 bytes
JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ
Básicamente un puerto del código anterior. No muy bien golfizado todavía. Pruébalo en línea
Expandido
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]])
Ahora, si Pyth tuviera una asignación múltiple a> 2 variables ...
P,K,L=map(int,input().split())Q=list(input()) l=[(L,0)]*K for j in range(len(Q)-L): if Q[j:j+L].count('#')<l[i][0]: l[i]=Q[j:j+L].count('#'),j del Q[l[i][1]:l[i][1]+L] print(sum([x[0]for x in l]))Q=list(input()) -> *Q,=input()Q[j:j+L].count('#')como una variable, 2)x=l[i][1];del Q[x:x+L],Haskell, 196 caracteres
Ejecuta todos los ejemplos.
Algo lento: O (2 ^ P) donde P es el tamaño del lote.
Probablemente queda mucho para jugar al golf aquí.
fuente