Courses

Dinamik program

Dinamik Programlamada Kalıplar - 2

Module: Dinamik Programlamada Kalıplar - 2

Problem

1 /5

oyunu doldur

Theory Click to read/hide

Sorumluluk Reddi: Aşağıda açıklanan yöntem evrensel değildir ancak genellikle bir sorunu çözebilir veya doğru çözüme ulaşmanıza yardımcı olabilir.

Bir problem sizden bir diziyi en iyi şekilde yok etmenizi/daraltmanızı/birleştirmenizi (veya benzerini) isterse, alt bölümlerde dinamik programlamayı kullanarak çözmeye çalışmalısınız.

dp[l][r]'yi bulalım - l'den r'ye indisleri olan bir alt segment için en uygun cevap. Dinamiklerin yeniden hesaplanması büyük ölçüde göreve bağlıdır, ancak aşağıdaki genel fikirler vardır:

1) l ve r uç elemanlarına bakın. Başka bir şekilde eşleşir veya tamamlarlarsa, dp[l][r] değerini dp[l+1][r-1] yoluyla güncellemek büyük olasılıkla mümkün olacaktır. Aksi takdirde dp[l][r-1] veya dp[l+1[r].
aracılığıyla
2) [l;r] segmentinin tek bir yapıyla temsil edilemediği sıklıkla olur. Daha sonra, bu alt parçanın tüm olası bölümlerini iki kısma ayırmak gerekir, yani l'den r-1'e kadar k elemanı üzerinde yineleme yapmak ve dp[l][r]'den dp[l][k] ve dp['ye kadar yeniden hesaplamak gerekir. k+1][r]. Daha küçük alt bölümlerde, bu bölümler de tasnif edildi, bu nedenle [l;r] alt bölümünü yalnızca iki parçaya değil, herhangi bir sayıda bölmeye ayırma seçenekleri dikkate alınır.

Problem

Soldan sağa 1'den n'ye kadar numaralandırılmış n renkli karelerden oluşan kareli bir kağıt şeridi veriliyor. i'inci kare başlangıçta c_i olarak renklendirilir.

c_i= c_j ve c_i= c_{k ise i ve j karelerinin aynı bileşende olduğunu söyleriz} i < k < J. Diğer bir deyişle i'den j'ye doğru doğru parçası üzerindeki tüm kareler aynı renge sahip olmalıdır.
Örneğin, şerit [3,3,3] 1 bağlı bileşene sahipken [5,2,4,4] 3 bileşene sahiptir.

Doldurma oyunu bu şeritte şu şekilde oynanır:
Oyunun başında rastgele bir başlangıç karesi seçersiniz (bu bir dönüş olarak sayılmaz).
Ardından, her harekette, başlangıç karesini içeren bağlı bileşenin rengini başka herhangi bir renkle değiştirirsiniz.

Tüm şeridi tek bir renkte yeniden renklendirmek için gereken minimum hamle sayısını öğrenin.

Giriş:
İlk satır, tek bir tamsayı n (1 ≤ n ≤ 5000) içerir — kare sayısı.

İkinci satır c₁,c₂,…,c_n tamsayılarını içerir (1 ≤ c_i <5000) — karelerin ilk renkleri.

Çıktı:
Tek bir tamsayı yazdır — yapılacak minimum hamle sayısı.

Örnekler:

Açıklama:
Birinci örnekteki optimal yollardan biri: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking