We have a row of 50 cells. Each cell is either left grey or covered by a red block, and every red block must have length at least 3. If two red blocks both appear, they must be separated by at least one grey cell. The all-grey arrangement is allowed, so the question is to count every valid coloring of the row under those rules.
The natural quantity to compute is \(F(n)\), the number of valid arrangements for a row of length \(n\). The goal of the problem is \(F(50)\).
The key is to choose a state that remembers only the remaining row length. Because every legal continuation depends solely on how many cells are left, dynamic programming gives an exact count with no overcounting.
Let \(F(n)\) be the number of valid fillings of a row of length \(n\). There is exactly one way to fill an empty row, so
$$F(0)=1.$$
For \(n=1\) and \(n=2\), no red block can fit, so the only arrangement is still the all-grey one:
$$F(1)=F(2)=1.$$
This already captures the most important invariant in the problem: once the left part of the row has been fixed legally, the remainder is just a smaller copy of the same counting problem.
To count \(F(n)\), inspect the leftmost cell.
If that cell is grey, the rest of the row is any valid arrangement of length \(n-1\), contributing \(F(n-1)\).
If the row starts with a red block of length \(b\), then \(b \ge 3\). Two cases occur:
If \(b=n\), the block fills the whole row, so this contributes exactly 1 arrangement.
If \(b \lt n\), then the next cell must be grey in order to separate this block from any later red block. After placing that mandatory grey separator, the remaining suffix has length \(n-b-1\), contributing \(F(n-b-1)\).
Therefore, for every \(n \ge 1\),
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
The sum is empty when \(n \lt 4\), which is exactly what we want. This recurrence is exhaustive and disjoint: every legal arrangement belongs to exactly one branch, determined by whether the row begins with grey or by the length of its first red block.
It is often clearer to rewrite the same formula with the suffix length \(r=n-b-1\):
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
Subtract the corresponding formula for \(F(n-1)\):
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
So the same counting sequence also satisfies
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
with initial values \(F(0)=1\), \(F(1)=1\), \(F(2)=1\), \(F(3)=2\). The implementations do not need this compressed form, but it is a useful mathematical check that the summation recurrence is internally consistent.
The implementations verify the checkpoint \(F(7)=17\), and the recurrence explains why. First compute the smaller values:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
Now split a row of length 7 by its first move:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
These terms correspond respectively to: first cell grey; first red block of length 3; length 4; length 5; length 6 followed by one forced grey; and a red block of length 7 filling the whole row. Substituting the known values gives
$$F(7)=11+2+1+1+1+1=17.$$
This example shows exactly how the recurrence mirrors the physical structure of the row.
The C++, Python, and Java implementations store the counts for all row lengths from 0 up to 50 in a one-dimensional table. The entry for length 0 is initialized to 1, and the table is then filled from left to right so that every transition reads only previously computed values.
For a fixed row length \(n\), the implementation begins with the contribution \(F(n-1)\), corresponding to a grey first cell. It then loops over every admissible red block length \(b\) from 3 to \(n\). If the block reaches the end of the row, it adds 1. Otherwise it adds the table entry for the remaining suffix of length \(n-b-1\), which already accounts for the mandatory grey separator after that first block.
After finishing all lengths up to 50, the final table entry is the answer. One implementation keeps the row length and minimum block size configurable, while the others hard-code the problem values, but all three evaluate the same recurrence and all three use the same checkpoint \(F(7)=17\).
For a general row length \(N\), the implementation computes \(F(1),F(2),\dots,F(N)\). For each \(n\), it may test every block length from 3 through \(n\), so the running time is
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
The memory usage is \(O(N)\) because only the one-dimensional dynamic-programming table is stored. In this problem \(N=50\), so the quadratic time bound is tiny in practice.
Gegeben ist eine Reihe mit 50 Feldern. Jedes Feld bleibt entweder grau oder wird von einem roten Block bedeckt. Jeder rote Block muss mindestens Länge 3 haben, und wenn zwei rote Blöcke vorkommen, muss zwischen ihnen mindestens ein graues Feld liegen. Auch die vollständig graue Reihe ist erlaubt. Gesucht ist also die Anzahl aller zulässigen Färbungen dieser Reihe.
Die natürliche Zählfunktion ist \(F(n)\), die Zahl der gültigen Belegungen einer Reihe der Länge \(n\). Das Problem verlangt den Wert \(F(50)\).
Die richtige Zustandsgröße ist allein die noch verbleibende Reihenlänge. Denn sobald ein Anfangsstück legal festgelegt ist, bleibt wieder exakt dieselbe Aufgabe auf einem kürzeren Restintervall übrig.
Sei \(F(n)\) die Anzahl gültiger Belegungen einer Reihe der Länge \(n\). Für die leere Reihe gibt es genau eine Möglichkeit, nämlich nichts zu platzieren:
$$F(0)=1.$$
Für \(n=1\) und \(n=2\) passt noch kein roter Block der Mindestlänge 3 hinein, also bleibt ebenfalls jeweils nur die komplett graue Belegung:
$$F(1)=F(2)=1.$$
Das ist die zentrale Invariante: Der Rest einer legal begonnenen Konfiguration ist immer wieder ein vollständiges Teilproblem derselben Art.
Um \(F(n)\) zu bestimmen, betrachtet man das linke Ende der Reihe.
Ist das erste Feld grau, dann folgt dahinter eine beliebige gültige Belegung der Länge \(n-1\). Dieser Fall liefert also \(F(n-1)\).
Beginnt die Reihe stattdessen mit einem roten Block der Länge \(b\), so gilt \(b \ge 3\). Dann gibt es zwei Unterfälle:
Wenn \(b=n\), füllt der Block die gesamte Reihe und trägt genau 1 bei.
Wenn \(b \lt n\), muss direkt danach ein graues Trennfeld stehen. Nach diesem Pflichtabstand bleibt ein Rest der Länge \(n-b-1\), der auf \(F(n-b-1)\) Arten gefüllt werden kann.
Damit erhält man für jedes \(n \ge 1\) die Rekurrenz
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
Für \(n \lt 4\) ist die Summe leer. Diese Fallunterscheidung ist vollständig und disjunkt: Jede zulässige Belegung wird genau einmal erfasst, entweder über ein graues Startfeld oder über die Länge des ersten roten Blocks.
Setzt man \(r=n-b-1\), dann wird dieselbe Formel zu
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
Subtrahiert man die entsprechende Gleichung für \(F(n-1)\), so folgt
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
Also erfüllt die Folge äquivalent auch
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
mit Startwerten \(F(0)=1\), \(F(1)=1\), \(F(2)=1\), \(F(3)=2\). Die Implementierungen benutzen weiterhin die Summenform, aber diese kürzere Rekurrenz ist eine nützliche mathematische Konsistenzprüfung.
Die Programme prüfen den Kontrollwert \(F(7)=17\). Zuerst braucht man die kleineren Werte:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
Dann zerlegt man die Reihe der Länge 7 nach dem ersten Schritt:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
Die Summanden stehen für: erstes Feld grau; erster roter Block mit Länge 3; Länge 4; Länge 5; Länge 6 mit anschließendem Pflichtgrau; sowie ein Block der Länge 7, der die Reihe vollständig füllt. Einsetzen ergibt
$$F(7)=11+2+1+1+1+1=17.$$
Genau daran sieht man, dass die Rekurrenz die reale Struktur der Anordnungen präzise abbildet.
Die C++-, Python- und Java-Implementierungen speichern die Werte für alle Reihenlängen von 0 bis 50 in einer eindimensionalen Tabelle. Der Eintrag für Länge 0 wird auf 1 gesetzt, danach werden die Werte in aufsteigender Reihenfolge berechnet, sodass jede Übergangsformel nur bereits bekannte Einträge liest.
Für eine feste Länge \(n\) startet die Berechnung mit dem Beitrag \(F(n-1)\) für ein graues erstes Feld. Danach testet die Implementierung jede zulässige Blocklänge \(b\) von 3 bis \(n\). Reicht der Block genau bis ans Ende, wird 1 addiert. Andernfalls wird der Tabellenwert für den Rest der Länge \(n-b-1\) addiert; darin ist das notwendige graue Trennfeld nach dem ersten Block bereits berücksichtigt.
Nach dem Ausfüllen aller Längen bis 50 ist der letzte Tabelleneintrag die gesuchte Antwort. Eine Implementierung hält Reihenlänge und Mindestblocklänge parametrisierbar, die anderen kodieren die Problemwerte direkt fest, aber alle drei berechnen dieselbe Rekurrenz und alle drei benutzen denselben Kontrollwert \(F(7)=17\).
Für eine allgemeine Reihenlänge \(N\) werden die Werte \(F(1),F(2),\dots,F(N)\) berechnet. Für jedes \(n\) können dabei alle Blocklängen von 3 bis \(n\) durchlaufen werden. Die Laufzeit ist also
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
Der Speicherverbrauch beträgt \(O(N)\), weil nur die eindimensionale Dynamik-Tabelle gehalten wird. Für das konkrete Problem mit \(N=50\) ist dieser Aufwand praktisch vernachlässigbar.
Uzunluğu 50 olan bir satır düşünelim. Her hücre ya gri bırakılır ya da kırmızı bir blok tarafından kaplanır. Her kırmızı blok en az 3 hücre uzunluğunda olmalıdır. İki kırmızı blok aynı yerleşimde bulunuyorsa, aralarında en az bir gri hücre bulunmak zorundadır. Tamamen gri düzen de geçerli olduğundan, soru bu kurallara uyan tüm yerleşimleri saymaktır.
Doğal sayım fonksiyonu \(F(n)\), uzunluğu \(n\) olan bir satır için geçerli düzen sayısıdır. Sorunun istediği değer \(F(50)\)'dir.
Bu problemde doğru durum uzayı yalnızca kalan uzunluktur. Çünkü satırın başı kurallara uygun biçimde yerleştirildikten sonra geriye yine aynı tipte, sadece daha kısa bir alt problem kalır.
\(F(n)\), uzunluğu \(n\) olan bir satırın geçerli doldurulma sayısı olsun. Boş satırı doldurmanın tam bir yolu vardır:
$$F(0)=1.$$
\(n=1\) ve \(n=2\) için uzunluğu en az 3 olan bir kırmızı blok sığamayacağı için tek seçenek yine tamamen gri düzendir:
$$F(1)=F(2)=1.$$
Buradaki temel değişmez şudur: Satırın sol tarafı yasal biçimde sabitlendikten sonra, kalan kısım aynı kurallara sahip bağımsız bir alt satırdır.
\(F(n)\)'i saymak için en soldaki hücreye bakmak yeterlidir.
İlk hücre gri ise, geriye uzunluğu \(n-1\) olan herhangi bir geçerli düzen kalır. Bu durum \(F(n-1)\) katkısı verir.
Satır bir kırmızı blokla başlıyorsa, bu bloğun uzunluğu \(b \ge 3\) olmalıdır. Burada iki alt durum vardır:
Eğer \(b=n\) ise blok bütün satırı kaplar ve katkı tam olarak 1'dir.
Eğer \(b \lt n\) ise bu bloktan sonra, sonraki kırmızı bloktan ayrımı sağlamak için zorunlu bir gri hücre gelmelidir. O gri ayırıcı yerleştirildikten sonra elde kalan uzunluk \(n-b-1\) olur ve katkı \(F(n-b-1)\)'dir.
Dolayısıyla her \(n \ge 1\) için
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
\(n \lt 4\) olduğunda toplam boştur. Bu ayrım hem tamdır hem de çakışmasızdır; her geçerli düzen ya gri bir hücreyle başlar ya da ilk kırmızı bloğunun uzunluğu tarafından tekil olarak belirlenir.
Aynı bağıntıyı, kalan kuyruk uzunluğunu \(r=n-b-1\) alarak şöyle de yazabiliriz:
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
Şimdi bunun \(F(n-1)\) için yazılmış halini çıkarırsak
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4)$$
elde edilir. Yani aynı dizi şu kısa bağıntıyı da sağlar:
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
başlangıç değerleri ise \(F(0)=1\), \(F(1)=1\), \(F(2)=1\), \(F(3)=2\)'dir. Uygulamalar doğrudan toplamlı hali kullanır; bu sıkıştırılmış biçim ise matematiksel bir doğrulama olarak faydalıdır.
Uygulamaların doğruladığı kontrol değeri \(F(7)=17\)'dir. Önce küçük değerleri bulalım:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
Ardından uzunluğu 7 olan satırı ilk karara göre ayıralım:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
Bu terimler sırasıyla şu durumları temsil eder: ilk hücre gri; ilk kırmızı blok uzunluğu 3; 4; 5; 6 olup ardından zorunlu bir gri gelir; ya da uzunluğu 7 olup satırı tamamen doldurur. Yerine koyarsak
$$F(7)=11+2+1+1+1+1=17$$
elde edilir. Böylece yinelemenin satırın gerçek yapısını birebir izlediği açıkça görülür.
C++, Python ve Java uygulamaları 0'dan 50'ye kadar tüm uzunluklar için sonuçları tek boyutlu bir tabloda saklar. Uzunluk 0 için değer 1 olarak başlatılır; sonra tablo soldan sağa doldurulur ve her yeni değer yalnızca daha önce hesaplanmış girdileri okur.
Sabit bir \(n\) için hesaplama önce gri başlangıç durumunu temsil eden \(F(n-1)\) katkısıyla başlar. Sonra uygulama, 3'ten \(n\)'e kadar tüm uygun kırmızı blok uzunluklarını dener. Blok tam sonda bitiyorsa 1 eklenir. Bitmiyorsa, ilk bloktan sonraki zorunlu gri ayırıcı da hesaba katılmış olacak şekilde, kalan \(n-b-1\) uzunluklu kuyruğun tablo değeri eklenir.
50'ye kadar bütün uzunluklar doldurulduğunda son tablo girdisi cevap olur. Uygulamalardan biri satır uzunluğu ile minimum blok boyunu parametreleştirir, diğerleri problem değerlerini sabit yazar; fakat üçü de aynı yinelemeyi değerlendirir ve üçü de \(F(7)=17\) kontrolünü kullanır.
Genel uzunluk \(N\) için uygulama \(F(1),F(2),\dots,F(N)\) değerlerini hesaplar. Her \(n\) için 3'ten \(n\)'e kadar blok boyları denenebildiğinden toplam çalışma süresi
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2)$$
olur. Bellek kullanımı yalnızca tek boyutlu dinamik programlama tablosu tutulduğu için \(O(N)\)'dir. Bu problemde \(N=50\) olduğundan gerçek çalışma maliyeti çok küçüktür.
Tenemos una fila de 50 casillas. Cada casilla puede quedar gris o quedar cubierta por un bloque rojo. Todo bloque rojo debe tener longitud al menos 3, y si aparecen dos bloques rojos, entre ellos debe haber al menos una casilla gris. También se permite la disposición completamente gris. La tarea consiste en contar todas las configuraciones válidas de la fila.
La función natural del problema es \(F(n)\), el número de arreglos válidos para una fila de longitud \(n\). Lo que se busca es \(F(50)\).
La elección correcta del estado es solamente la longitud restante de la fila. Una vez que el prefijo ya se colocó legalmente, el sufijo pendiente vuelve a ser exactamente el mismo problema, solo que más corto.
Sea \(F(n)\) el número de formas válidas de rellenar una fila de longitud \(n\). Para la fila vacía hay exactamente una posibilidad:
$$F(0)=1.$$
Para \(n=1\) y \(n=2\), ningún bloque rojo de longitud mínima 3 puede entrar, así que la única configuración sigue siendo la totalmente gris:
$$F(1)=F(2)=1.$$
Esta es la invariante central del problema: después de fijar legalmente la parte izquierda de la fila, la parte restante es una copia completa del mismo conteo combinatorio.
Para contar \(F(n)\), basta mirar la primera casilla.
Si esa casilla es gris, el resto de la fila puede ser cualquier arreglo válido de longitud \(n-1\). Ese caso aporta \(F(n-1)\).
Si la fila empieza con un bloque rojo de longitud \(b\), entonces \(b \ge 3\). Aquí aparecen dos posibilidades:
Si \(b=n\), el bloque llena toda la fila y aporta exactamente 1.
Si \(b \lt n\), la casilla siguiente debe ser gris para separar ese bloque de cualquier bloque rojo posterior. Después de colocar ese separador obligatorio, queda un sufijo de longitud \(n-b-1\), que aporta \(F(n-b-1)\).
Por tanto, para todo \(n \ge 1\),
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
Cuando \(n \lt 4\), la suma es vacía. Esta partición es exhaustiva y disjunta: cada arreglo válido cae exactamente en una rama, determinada por si empieza en gris o por la longitud de su primer bloque rojo.
Si reindexamos con \(r=n-b-1\), la misma fórmula se convierte en
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
Restando la ecuación correspondiente para \(F(n-1)\), obtenemos
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
Así, la misma sucesión satisface también
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
con valores iniciales \(F(0)=1\), \(F(1)=1\), \(F(2)=1\), \(F(3)=2\). Las implementaciones no necesitan esta forma comprimida, pero sirve como una comprobación matemática útil del conteo principal.
Las implementaciones verifican el punto de control \(F(7)=17\), y la recurrencia explica el motivo. Primero se calculan los valores menores:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
Ahora dividimos la fila de longitud 7 según su primer movimiento:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
Estos términos representan, respectivamente: primera casilla gris; primer bloque rojo de longitud 3; longitud 4; longitud 5; longitud 6 seguido por un gris obligatorio; y un bloque de longitud 7 que llena toda la fila. Sustituyendo, queda
$$F(7)=11+2+1+1+1+1=17.$$
El ejemplo muestra con claridad que la recurrencia no es una plantilla abstracta, sino la traducción exacta de cómo puede empezar una disposición válida.
Las implementaciones en C++, Python y Java guardan los conteos para todas las longitudes desde 0 hasta 50 en una tabla unidimensional. El valor de longitud 0 se inicia en 1 y, a continuación, la tabla se rellena en orden creciente, de modo que cada transición usa únicamente resultados ya calculados.
Para una longitud fija \(n\), la implementación empieza con la contribución \(F(n-1)\), correspondiente a dejar gris la primera casilla. Después prueba todos los tamaños de bloque \(b\) desde 3 hasta \(n\). Si el bloque llega exactamente al final, suma 1. En caso contrario, suma la entrada de la tabla para el sufijo restante de longitud \(n-b-1\), donde ya queda incorporada la casilla gris obligatoria tras ese primer bloque.
Una vez completadas todas las longitudes hasta 50, la última entrada de la tabla es la respuesta. Una de las implementaciones deja configurables la longitud de la fila y la longitud mínima del bloque; las otras fijan directamente los valores del problema. En todos los casos se evalúa la misma recurrencia y se comprueba el mismo valor \(F(7)=17\).
Para una fila general de longitud \(N\), se calculan \(F(1),F(2),\dots,F(N)\). Para cada \(n\), pueden recorrerse todos los tamaños de bloque entre 3 y \(n\), así que el tiempo total es
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
El espacio usado es \(O(N)\), porque solo se almacena una tabla de programación dinámica de una dimensión. En el caso concreto \(N=50\), este costo es muy pequeño.
题目给出一行长度为 50 的方格。每个位置要么保持灰色，要么被某个红色块覆盖。每个红色块的长度至少为 3；如果一行中出现多个红色块，那么任意两个红色块之间至少要隔开一个灰色方格。全灰方案也算一种合法排列。问题就是在这些约束下，长度 50 的整行一共有多少种合法摆放方式。
最自然的计数对象是 \(F(n)\)，表示长度为 \(n\) 的一行的合法安排数。原题要求的就是 \(F(50)\)。
这个问题真正需要记录的信息只有“还剩多少格没有处理”。因为一旦左边前缀已经合法放好，右边剩余部分面对的就是一个完全同型、只是规模更小的子问题。这正是动态规划能够精确计数的原因。
令 \(F(n)\) 表示长度为 \(n\) 的一行的合法填法数量。空行只有一种填法，也就是什么都不放，所以
$$F(0)=1.$$
当 \(n=1\) 或 \(n=2\) 时，长度至少为 3 的红块根本放不进去，因此唯一的合法方案仍然是全灰：
$$F(1)=F(2)=1.$$
这里的核心不变量是：任何一个已经合法完成的前缀，都会把剩余部分变成同一类型的计数问题，而不会引入新的全局条件。
为了求 \(F(n)\)，只需看最左边的位置怎么处理。
如果第一格是灰色，那么其余 \(n-1\) 格可以是任意合法安排，因此这一类贡献是 \(F(n-1)\)。
如果一开始就放一个红块，设它的长度为 \(b\)，那么必须有 \(b \ge 3\)。这时又分成两种情况：
如果 \(b=n\)，说明这个红块刚好铺满整行，于是这一种只贡献 1。
如果 \(b \lt n\)，那么这个红块后面必须立即跟一个灰格，作为与后续红块之间的强制分隔。放完这个灰色分隔以后，右边剩下的长度就是 \(n-b-1\)，其贡献为 \(F(n-b-1)\)。
因此，对所有 \(n \ge 1\)，都有
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
当 \(n \lt 4\) 时，上面的求和自然为空。这个分类既没有遗漏，也不会重复，因为每个合法方案都能由“第一格是否灰色”或“第一个红块的长度”唯一确定。
如果把剩余后缀长度记成 \(r=n-b-1\)，同一个公式可以重写为
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
再减去 \(F(n-1)\) 的对应公式，就得到
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
于是这组计数同时满足更短的线性递推
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
初值为 \(F(0)=1\)、\(F(1)=1\)、\(F(2)=1\)、\(F(3)=2\)。实现代码并不依赖这个压缩版本，但它提供了一个很好的数学交叉验证，说明原始求和递推是自洽的。
实现里会核对检查点 \(F(7)=17\)，这个值可以直接由递推解释出来。先算出较小项：
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
然后按第一步如何选择，把长度 7 的一行拆开：
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
这些项依次对应于：第一格为灰；第一个红块长度为 3；长度为 4；长度为 5；长度为 6 且后面必须放一个灰格；以及长度为 7、直接铺满整行的情况。代入数值可得
$$F(7)=11+2+1+1+1+1=17.$$
这个例子说明，递推式中的每一项都对应着一类清晰可见的实际摆放，而不是抽象地“凑”出来的公式。
C++、Python 和 Java 三个实现都使用一个一维表，保存从长度 0 到长度 50 的所有答案。长度 0 的值先设为 1，然后按长度递增的顺序依次填表，这样在计算某个 \(F(n)\) 时，所需的所有更短长度结果都已经可用。
对固定的 \(n\)，实现先把“第一格灰色”的贡献 \(F(n-1)\) 放进去。接着遍历所有可行的红块长度 \(b\)，其中 \(3 \le b \le n\)。如果这个红块正好顶到最右端，就加 1；如果没有顶到最右端，就加上剩余后缀长度 \(n-b-1\) 的表项。这里之所以是 \(n-b-1\)，正是因为第一个红块后面必须预留一个灰色分隔格。
把 1 到 50 的所有长度都填完后，最后一个表项就是答案。三个实现的写法略有差异，其中一个把总长度和最小红块长度写成可调参数，另外两个直接固定为题目的 50 和 3，但它们计算的都是同一个递推，并且都以 \(F(7)=17\) 作为一致性检查。
如果把行长记为一般的 \(N\)，实现会计算 \(F(1),F(2),\dots,F(N)\)。对每个 \(n\)，内部都可能枚举从 3 到 \(n\) 的所有红块长度，因此总时间复杂度为
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
空间复杂度是 \(O(N)\)，因为只保存了一维动态规划表。在本题的 \(N=50\) 下，这个代价非常小。
Есть ряд длины 50 клеток. Каждая клетка либо остается серой, либо покрывается красным блоком. Длина каждого красного блока должна быть не меньше 3. Если в раскладке присутствуют два красных блока, между ними обязана стоять хотя бы одна серая клетка. Полностью серый ряд тоже считается допустимым. Нужно посчитать число всех корректных раскладок.
Естественная функция для такого подсчета - \(F(n)\), количество допустимых заполнений ряда длины \(n\). В задаче требуется найти \(F(50)\).
Правильное состояние здесь определяется только длиной еще не обработанного хвоста. Как только левый префикс размещен корректно, оставшаяся часть снова является точно такой же задачей, только меньшего размера. Поэтому динамическое программирование считает все варианты без пропусков и без повторного учета.
Обозначим через \(F(n)\) число допустимых заполнений ряда длины \(n\). Для пустого ряда есть ровно один вариант:
$$F(0)=1.$$
При \(n=1\) и \(n=2\) красный блок минимальной длины 3 не помещается, значит остается только полностью серый ряд:
$$F(1)=F(2)=1.$$
Главный инвариант таков: после любого корректно построенного начала оставшийся хвост зависит только от своей длины, а не от более сложной истории расположения блоков.
Чтобы посчитать \(F(n)\), достаточно посмотреть, что происходит в первой клетке.
Если первая клетка серая, то оставшиеся \(n-1\) клеток образуют любой допустимый ряд длины \(n-1\). Вклад этого случая равен \(F(n-1)\).
Если ряд начинается с красного блока длины \(b\), то обязательно \(b \ge 3\). Тогда есть два подслучая:
Если \(b=n\), блок полностью заполняет весь ряд и дает вклад 1.
Если \(b \lt n\), то следующая клетка обязана быть серой, чтобы отделить этот блок от любого последующего красного блока. После такого обязательного разделителя остается хвост длины \(n-b-1\), который можно заполнить \(F(n-b-1)\) способами.
Следовательно, для всех \(n \ge 1\) имеем
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
При \(n \lt 4\) сумма пуста. Это разбиение одновременно полное и непересекающееся: каждая допустимая раскладка определяется либо серой первой клеткой, либо длиной первого красного блока.
Если ввести длину оставшегося хвоста \(r=n-b-1\), то та же формула перепишется как
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
Вычитая из нее аналогичную формулу для \(F(n-1)\), получаем
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
Значит, та же последовательность удовлетворяет и более короткому виду
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
с начальными значениями \(F(0)=1\), \(F(1)=1\), \(F(2)=1\), \(F(3)=2\). Реализации напрямую используют исходную суммирующую формулу, но этот сжатый вид удобен как математическая проверка.
В программах проверяется контрольное значение \(F(7)=17\). Сначала вычислим более короткие случаи:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
Теперь разложим ряд длины 7 по первому действию:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
Эти слагаемые соответствуют случаям: первая клетка серая; первый красный блок длины 3; длины 4; длины 5; длины 6 с обязательной серой клеткой после него; и блок длины 7, заполняющий весь ряд. Подставляя значения, получаем
$$F(7)=11+2+1+1+1+1=17.$$
Пример показывает, что рекуррентность буквально повторяет геометрию ряда и правило обязательного разделителя.
Реализации на C++, Python и Java хранят ответы для всех длин от 0 до 50 в одномерной таблице. Значение для длины 0 инициализируется единицей, после чего таблица заполняется по возрастанию длины, так что каждый новый переход обращается только к уже вычисленным значениям.
Для фиксированной длины \(n\) вычисление начинается со вклада \(F(n-1)\), отвечающего серой первой клетке. Затем перебираются все допустимые длины первого красного блока \(b\) от 3 до \(n\). Если блок доходит ровно до конца ряда, прибавляется 1. Иначе прибавляется табличное значение для хвоста длины \(n-b-1\); это именно тот случай, когда после первого блока уже учтена обязательная серая разделительная клетка.
После заполнения значений до длины 50 последняя ячейка таблицы и есть ответ. В одной реализации длина ряда и минимальная длина блока задаются параметрами, а в двух других используются фиксированные значения задачи, но во всех трех случаях вычисляется одна и та же рекуррентность и проверяется одно и то же значение \(F(7)=17\).
Для общей длины ряда \(N\) вычисляются значения \(F(1),F(2),\dots,F(N)\). Для каждого \(n\) может перебираться каждый размер блока от 3 до \(n\), поэтому суммарное время равно
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
Память имеет порядок \(O(N)\), поскольку хранится только одномерная таблица динамического программирования. При \(N=50\) эта стоимость на практике очень мала.
لدينا صف طوله 50 خانة. كل خانة إما أن تبقى رمادية أو أن تُغطى بكتلة حمراء. طول كل كتلة حمراء يجب أن يكون على الأقل 3، وإذا ظهرت كتلتان حمراوان أو أكثر في الترتيب نفسه فلا بد من وجود خانة رمادية واحدة على الأقل بين كل كتلتين. كما أن الترتيب الرمادي بالكامل مسموح. المطلوب هو عد جميع الترتيبات الصحيحة التي تحقق هذه الشروط.
الكمية الطبيعية للحساب هي \(F(n)\)، أي عدد الترتيبات الصالحة لصف طوله \(n\). هدف المسألة هو إيجاد \(F(50)\).
الحالة المناسبة هنا لا تحتاج إلا إلى طول الجزء المتبقي من الصف. فبمجرد أن نثبت مقدمة الصف بطريقة قانونية، يصبح ما تبقى مسألة من النوع نفسه تمامًا ولكن على طول أصغر. لهذا يكون البرمجة الديناميكية وصفًا دقيقًا للمسألة لا فيه فقدان ولا فيه تكرار.
لنعرّف \(F(n)\) على أنه عدد طرق ملء صف طوله \(n\) بصورة صحيحة. الصف الفارغ له طريقة واحدة فقط، وهي عدم وضع أي شيء:
$$F(0)=1.$$
وعندما يكون \(n=1\) أو \(n=2\)، لا يمكن إدخال كتلة حمراء لأن الحد الأدنى لطولها هو 3، ولذلك يبقى الترتيب الوحيد هو الصف الرمادي بالكامل:
$$F(1)=F(2)=1.$$
الثابت الأساسي في الحل هو أن أي جزء متبق بعد مقدمة صحيحة يعتمد فقط على طوله، ولا يعتمد على تفاصيل أخرى من الماضي.
لحساب \(F(n)\)، ننظر إلى الخانة الأولى فقط.
إذا كانت الخانة الأولى رمادية، فإن بقية الصف يمكن أن تكون أي ترتيب صحيح بطول \(n-1\). مساهمة هذا الفرع هي \(F(n-1)\).
أما إذا بدأ الصف بكتلة حمراء طولها \(b\)، فلا بد أن يكون \(b \ge 3\). وهنا حالتان:
إذا كان \(b=n\)، فالكتلة تملأ الصف كله، ومساهمة هذا الفرع تساوي 1 بالضبط.
إذا كان \(b \lt n\)، فيجب أن تأتي بعدها مباشرة خانة رمادية تفصلها عن أي كتلة حمراء لاحقة. وبعد وضع هذا الفاصل الإجباري يبقى جزء طوله \(n-b-1\)، وعدد ترتيباته هو \(F(n-b-1)\).
إذًا لكل \(n \ge 1\) نحصل على
$$\boxed{F(n)=F(n-1)+\sum_{b=3}^{n-1} F(n-b-1)+1.}$$
وعندما يكون \(n \lt 4\) يكون الجمع فارغًا بطبيعته. هذا التقسيم شامل وغير متداخل: كل ترتيب صحيح ينتمي إلى فرع واحد فقط، يحدده إما كون الخانة الأولى رمادية أو طول أول كتلة حمراء.
إذا كتبنا طول الذيل المتبقي على صورة \(r=n-b-1\)، فإن الصيغة نفسها تصبح
$$F(n)=F(n-1)+1+\sum_{r=0}^{n-4} F(r)\qquad (n \ge 1).$$
وبطرح المعادلة المناظرة لـ \(F(n-1)\) نحصل على
$$F(n)-F(n-1)=F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4).$$
ومن ثم فإن المتتالية نفسها تحقق أيضًا
$$\boxed{F(n)=2F(n-1)-F(n-2)+F(n-4)\qquad (n \ge 4),}$$
مع القيم الابتدائية \(F(0)=1\)، \(F(1)=1\)، \(F(2)=1\)، \(F(3)=2\). الشيفرات لا تحتاج إلى هذه الصورة المختصرة، لكنها مفيدة كتحقق رياضي من اتساق صيغة العد الأساسية.
تتحقق التطبيقات من القيمة الاختبارية \(F(7)=17\)، ويمكن فهمها مباشرة من التكرار. أولًا نحسب القيم الأصغر:
$$F(3)=2,\qquad F(4)=4,\qquad F(5)=7,\qquad F(6)=11.$$
ثم نفكك صف الطول 7 بحسب بدايته:
$$F(7)=F(6)+F(3)+F(2)+F(1)+F(0)+1.$$
تمثل هذه الحدود على الترتيب: أن تبدأ الخانة الأولى رمادية؛ أو أن يكون طول أول كتلة حمراء 3؛ أو 4؛ أو 5؛ أو 6 يتبعها فاصل رمادي إجباري؛ أو 7 فتملأ الصف كله. بالتعويض نحصل على
$$F(7)=11+2+1+1+1+1=17.$$
وهذا المثال يوضح أن كل حد في التكرار له معنى تركيبي مباشر مرتبط ببنية الصف الفعلية.
تحتفظ تطبيقات C++ وPython وJava بكل القيم من الطول 0 حتى الطول 50 في جدول أحادي البعد. تُهيَّأ قيمة الطول 0 بالعدد 1، ثم يُملأ الجدول تصاعديًا بحيث إن كل انتقال يعتمد فقط على قيم سبق حسابها.
لطول ثابت \(n\)، يبدأ الحساب بالمساهمة \(F(n-1)\) الخاصة بحالة أن تكون الخانة الأولى رمادية. بعد ذلك تُجرَّب جميع أطوال الكتل الحمراء المسموح بها من 3 حتى \(n\). إذا وصلت الكتلة إلى نهاية الصف تمامًا أُضيفت قيمة 1. وإذا لم تصل، أُضيفت قيمة الذيل المتبقي بطول \(n-b-1\)، وهو الذيل الذي يأتي بعد احتساب الخانة الرمادية الفاصلة الإلزامية مباشرة بعد أول كتلة.
بعد إكمال القيم حتى 50 تكون آخر خانة في الجدول هي الجواب. إحدى التطبيقات تجعل طول الصف والحد الأدنى لطول الكتلة قابلين للضبط، بينما تثبت التطبيقات الأخرى قيم المسألة مباشرة، لكن الجميع يحسب التكرار نفسه ويستخدم نقطة التحقق نفسها \(F(7)=17\).
إذا رمزنا لطول الصف العام بالرمز \(N\)، فإن التنفيذ يحسب \(F(1),F(2),\dots,F(N)\). ولكل \(n\)، قد يمر على كل أطوال الكتل من 3 حتى \(n\)، ولذلك يكون الزمن الكلي
$$O\!\left(\sum_{n=1}^{N} n\right)=O(N^2).$$
أما الذاكرة فهي \(O(N)\)، لأن المخزن الوحيد هو جدول البرمجة الديناميكية الأحادي. وفي المسألة الحالية حيث \(N=50\)، يكون هذا التعقيد صغيرًا جدًا عمليًا.