算法合集之《淺析信息學(xué)中的“分”與“合”》(文件)
【正文】 2MN)！ 100 1000) [例三 ]最優(yōu)序列 —— “ 分”繁為簡(jiǎn) ?動(dòng)態(tài)規(guī)劃之所以不可行，原因在于 —— 題目中 K和 M的范圍太大了！ ?利用“分”的思想，我們嘗試限制 K，令 K=1，也就是對(duì)于長(zhǎng)度為 M的子串，最多只選一個(gè)元素作為原題的一個(gè)子問(wèn)題： [例三 ]最優(yōu)序列 —— 子問(wèn)題 ?給定一個(gè)長(zhǎng)度為 N的正整數(shù)序列。 “分治法”是運(yùn)用“分”與“合”思想方法解題的重要應(yīng)用，此外，“分”與“合”的思想方法還有更多、更廣泛的應(yīng)用。淺析信息學(xué)中的“分”與“合” 福建省福州第三中學(xué) 楊沐 引言 ?分 ?“分”的思想是將一個(gè)難以直接解決的大問(wèn)題，轉(zhuǎn)化成一些規(guī)模較小或限制某些條件的子問(wèn)題來(lái)思考，以求將問(wèn)題解決。 N,K限制下最優(yōu)化問(wèn)題 → N,K,Len限制下存在性問(wèn)題 規(guī)模為 n的問(wèn)題 → 規(guī)模為 n1的問(wèn)題 [例三 ]最優(yōu)序列 ?給定一個(gè)長(zhǎng)度為 N的正整數(shù)序列。 ?求一個(gè)子序列，使得原序列中任意長(zhǎng)度為 M的子串中被選出的元素不超過(guò) 1個(gè)。 ? 引理一 原問(wèn)題的任意一組解都可以由 K組不
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1