浅析信息学中的分与合.ppt

浅祈信息学中的“分”与
合
福建省福州第三中学
杨沐
引言
冷分
合分会
分”的思想是将
小问题
的解决合并成一个
制某些条件的子问
大问题,从而取得
题来思考,以求将整个问题的解决。
问题解决。
引言
冷运用“分”与“合”思想方法解题的精髓在
于通过在“分?[例“耷奶模的转化,找出
解染触辅题丛解限靜在@善法
△
应用,此外,姆]的的思想方法
樗岁的的壓n-1的问题
[例三最优序列
[例三最优序列
给定一个长度为N的正整数序列。
求一个子序列,使得原序列中任意长度为M
的子串中被选出的元素不超过K个。
要求选出的元素之和最大。
数据范围
1≤N≤1000
1≤K,M≤100
[例三最优序列
输入数据:
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
[例三最优序列——分析
动态规划0)
线段树?-无从入手
g
怎么办?
分”g
[例三最优序列“分”繁为简
动态规划之所以不可行,原因在于—题目
中K和M的范围太大了!
利用“分”的思想,我们尝试限制K,令K=1,
也就是对于长度为M的子串,最多只选一个
元素作为原题的一个子问题:
[例三最优序列——子问题
给定一个长度为N的正整数序列。
求一个子序列,使得原序列中任意长度为M
的子串中被选出的元素不超过1个。
要求选出的元素之和最大。
数据范围
1≤N≤1000
1≤M≤100
[例三最优序列—“分”繁为简
令对于这个子问题,由于K做了限制,我们可
以用动态规划来解决这个问题。
冷设dp订表示前个元素,在满足题意的前提下选出的最大和
dp[=max(dp[i-1], dp[i-M]+value[)
iM
dp=max(dpti-1l, valueD
0<i<M
dp[oJ=0
[例三最优序列—进一步分析
K
子问题
原问题
是否可以通过求解K次的子问题从
而解决原题呢?