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