edilemiyor

Question

dün gece nedeniyle dinamik programlama atama vardı, ama son sorunu çözmek için nasıl anlayamadık çünkü bitmemiş içinde açmak zorunda kaldı:

devlet izlemek istiyor karayolu üzerinde mil uzunluğunda trafik. Otoyolun kilometresine bir izleme cihazı kurmak için _i maliyetine sahiptir. İzleme cihazları arasındaki maksimum mesafe d milden fazla olmamalıdır. Yani, eğer mil üzerinde bir izleme cihazı varsa, o zaman, i + 1'den mile i + d'ye kadar bir izleme cihazı olmalıdır (ya da i + d> n). Devlet, maliyeti en aza indirecek bir plan istiyor. Maliyetlerin bir C [1..n] dizisi olduğunu varsayalım. Bir k mil karayolunu varsayarak en iyi çözümün bedeli olmak ve k k milinde bir izleme cihazını varsaymak için, v _{v d izin verin. Verilen C ve d, v v vk-1 arasındaki değerlerin biliniyorsa, v k'un değerinin nasıl belirleneceğini gösterir. Bunu matematiksel olarak yazabilir veya kitabın stilinde sözde kod yazabilirsiniz. K = 1 ila k = n arasındaki olası tüm k değerleri dikkate almanız gerektiğine dikkat edin.}

Ben buna benzer bir sorun geliyor sınavda yer eminim ve ben en azından bu çözme başlamak için nerede olduğunu bilmek istiyoruz, bu nedenle herhangi bir yardım takdir edilmektedir.

Answer 1

DP tanımlayalım [i] istasyonunda bir monitör yükleme az maliyetle, i ve daha ucuz olan başka dizinler i (örneğin, birbirini takip eden her istasyon daha az ya da bir d mesafesinde eşit olduğunu) şimdi

(-, [d n + 1] ... [n - 2] DP DP, [n - 1] DP, [n] DP) bizim sorunun cevabı

dakika olacaktır

olduğu Son monitörün son d indeksine sahip olmasının minimum maliyeti.

Şimdi, dinamik programlama için tekrarlama ilişki kolaylıkla görülebileceği gibi:

DP [i] = dakika (DP [i - 1], DP [i - 2], ... DP [i - d]) + C [i] Eğer indeks üzerinde bir monitör kurmak istiyorsak, bunu C [i] maliyetine yüklüyoruz ve ayrıca önceki d indekslerinde bir monitörümüz olduğundan emin olmalıyız. Bu yüzden, ikinci son monitörün önceki d dizinlerine yüklenmesi en azını alıyoruz.

Yinelemeyi naif yöntemle kodlarsanız, O (n * d) görünür, ancak çift uçlu bir kuyruk kullanarak kayan pencere minimum algoritmasını kullanarak, zaman karmaşıklığını asimptotik olarak O (n) olarak azaltabilirsiniz.

Bu bir atama problemi olduğundan, ayrıntılı bir şekilde yazmam. Bu noktadan takip edebilmelisiniz.