算法合集之《淺析信息學中的“分”與“合”》-文庫吧
2025-09-19 18:36 本頁面
【正文】 之和最大。 ?數據范圍： 1≤N≤1000 1≤K， M≤100 [例三 ]最優(yōu)序列 ?輸入數據： 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)序列 —— 分析 動態(tài)規(guī)劃 線段樹？ 怎么辦？ “ 分 ” 超時 無從入手 O(2MN)！ 100 1000) [例三 ]最優(yōu)序列 —— “ 分”繁為簡 ?動態(tài)規(guī)劃之所以不可行，原因在于 —— 題目中 K和 M的范圍太大了！ ?利用“分”的思想，我們嘗試限制 K，令 K=1，也就是對于長度為 M的子串，最多只選一個元素作為原題的一個子問題： [例三 ]最優(yōu)序列 —— 子問題 ?給定一個長度為 N的正整數序列。 ?求一個子序列，使得原序列中任意長度為 M的子串中被選出的元素不超過 1個。 ?要求選出的元素之和最大。 ?數據范圍： 1≤N≤1000 1≤
教學課件相關推薦
鄂ICP備17016276號-1