算法合集之淺析信息學(xué)中的“分”與“合”(完整版)
【正文】 N=10， M=4， K=2 {7， 3， 4， 8， 2， 6， 5， 7， 4， 8} ?輸出答案： 36 ? {7， 3， 4， 8， 2， 6， 5， 7， 4， 8} [例三 ]最優(yōu)序列 —— 分析 動(dòng)態(tài)規(guī)劃 線段樹？ 怎么辦？ “ 分 ” 超時(shí) 無(wú)從入手 O(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ù)序列。淺析信息學(xué)中的“分”與“合” 福建省福州第三中學(xué) 楊沐 引言 ?分 ?“分”的思想是將一個(gè)難以直接解決的大問(wèn)題，轉(zhuǎn)化成一些規(guī)模較小或限制某些條件的子問(wèn)題來(lái)思考，以求將問(wèn)題解決。 ?求一個(gè)子序列，使得原序列中任意長(zhǎng)度為 M的子串中被選出的元素
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1