浅谈数据的合理组织ppt课件

1、浅谈数据的合理组织浅谈数据的合理组织.引子引子标题越来越难标题越来越难数据关系越来越复杂！数据关系越来越复杂！对组织数据的要求越来越高！对组织数据的要求越来越高！合理组织在解题中越来越重要！合理组织在解题中越来越重要！.【题意描画】【题意描画】给出给出N个物品，每个物品都有一个权值个物品，每个物品都有一个权值(50000)和一个价钱和一个价钱(10000)。我们称可以直接被购买的物品为主件，称不能被直。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只需当其主件被购买了才干被购买，接购买的物品为附件，附件只需当其主件被购买了才干被购买，一个主件最多有两个附件，附件没有下一级

2、附件。一个主件最多有两个附件，附件没有下一级附件。【义务】【义务】用不超越用不超越M元钱，购买一些物品，使得被购买的物品的总权值最元钱，购买一些物品，使得被购买的物品的总权值最大。大。金明的预算方案金明的预算方案【数据规模】【数据规模】N60 M3200.标题中给出的主件与附件间构成树形构造，而一切的物品间构成森林构造。为了方便起见，我们给一切的主件都加上一个“上级主件，这样，一切的物品构成了一棵树。数据的初步组织数据的初步组织.树形动态规划算法树形动态规划算法!算法算法1形状形状FijFij表示给以表示给以i i为根的子树，总共破费不超越为根的子树，总共破费不超越j j元，元，所能获得的最大

3、权值和。所能获得的最大权值和。?枚举量太大，效率不高！枚举量太大，效率不高！总破费不超越总破费不超越j.用左儿子右兄弟表示法来表示这一棵树！用左儿子右兄弟表示法来表示这一棵树！时间复杂度为时间复杂度为 O(NM2) O(NM2)形状总数形状总数 O(MN) O(MN)形状转移代价形状转移代价 O(M) O(M)N*M*M=6*108，不太理想。，不太理想。形状形状FijFij表示以表示以i i为根的子树总共破费为根的子树总共破费j j元能获得的最大权值和。元能获得的最大权值和。我们只需求枚举给左子树分配多少钱，剩下的钱都分给右子树。我们只需求枚举给左子树分配多少钱，剩下的钱都分给右子树。.我们

4、把配套的主件和附件看成一组。这样，显然对于每一组，能够的购买方案最多只需如下五种：我们换一种数据组织方式我们换一种数据组织方式1.附件没有附件。附件没有附件。2.每个主件最多只需两个附件。每个主件最多只需两个附件。思索此题特殊条件：1.什么都不买什么都不买2.只购买主件只购买主件3.购买主件和附件购买主件和附件14.购买主件和附件购买主件和附件25.全购买全购买.类似经典的类似经典的-背包问题！背包问题！组织数据后，我们可以得到复杂度为组织数据后，我们可以得到复杂度为O(NM)O(NM)的优秀算法的优秀算法 形状总数形状总数 O(MN) 形状转移代价形状转移代价 O(1).郁闷的金明郁闷的金明

5、【题意描画】【题意描画】给出给出N个物品，每个物品都有一个权值个物品，每个物品都有一个权值(50000)和一个价钱和一个价钱(10000)。我们称可以直接被购买的物品为主件，称不能被直。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只需当其主件被购买了才干被购买，接购买的物品为附件，附件只需当其主件被购买了才干被购买，主件可以有恣意多附件，附件没有下一级附件。主件可以有恣意多附件，附件没有下一级附件。【义务】【义务】用不超越用不超越M元钱，购买一些物品，使得被购买的物品的总权值最元钱，购买一些物品，使得被购买的物品的总权值最大。大。【数据规模】【数据规模】N60 M320

6、0.标题放宽了“一个主件最多可以有两个附件这个限制。问题分析问题分析数据组织方式数据组织方式依然适用效率以物品为节点的树形构造以组为元素的序列-我们回想上题的数据组织方式。.重新安排这些物品的顺序，使得每个附件都紧跟其主件，保证其前面的最近的主件就是它附属的主件。如以下图：数据组织方案二数据组织方案二主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件树树序列序列.形状形状Fijk表示从第表示从第i个物品到第个物品到第n个物品，最多破费个物品，最多破费j元，元，k表示表示i物品前面的主件有没有被购买，的最大价值和。物品前面的主件有没有被购买，的最大价值和。这样

7、组织数据以后，一个附件能被购买的必要条件是这样组织数据以后，一个附件能被购买的必要条件是“其前面的最其前面的最近的主件被购买了。近的主件被购买了。算法算法3主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件K=0 主件主件2没有被购买没有被购买K=1 主件主件2有被购买有被购买. 形状总数形状总数 O(NM*2) 形状转移代价形状转移代价O(1) 时间复杂度时间复杂度 O(NM)算法算法3重新组织数据后，我们再次胜利地设重新组织数据后，我们再次胜利地设计出了计出了O(NM)的算法。的算法。.【题意描画】【题意描画】给出给出N个物品，每个物品都有一个权值个物品

8、，每个物品都有一个权值(50000)和一个价钱和一个价钱(10000)。我们称可以直接被购买的物品为主件，称不能被直。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只需当其主件被购买了才干被购买，接购买的物品为附件，附件只需当其主件被购买了才干被购买，主件可以有恣意多附件，可以有多级附件。主件可以有恣意多附件，可以有多级附件。很郁闷的金明很郁闷的金明【义务】【义务】用不超越用不超越M元钱，购买一些物品，使得被购买的物品的总权值最元钱，购买一些物品，使得被购买的物品的总权值最大。大。【数据规模】【数据规模】N60 M3200.如今的标题在原题的根底条件上不仅添加附件的个数，

9、还出现如今的标题在原题的根底条件上不仅添加附件的个数，还出现了多级附件。了多级附件。问题分析问题分析这是很普通的树！这是很普通的树！.普通的树形构造，我们还能不能用前面的数据组普通的树形构造，我们还能不能用前面的数据组织方式呢？织方式呢？数据组织方式数据组织方式依然适用效率以物品为节点的树形构造以组为元素的序列附件紧跟其主件的序列阐明这些数据组织方式都不合理，需求再次重新组织数据！阐明这些数据组织方式都不合理，需求再次重新组织数据！.如今我们再回过头来研讨一下前面一种数据组织方式：把同在一个组的主件放在附件的前面，将树形问题转化到序列上来。而如今的问题是：树的高度添加了。组织数据方案三组织数据

10、方案三思索：树的先根遍历序。思索：树的先根遍历序。.仔细思索算法仔细思索算法3的形状转移：的形状转移：主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件K=0迁移到此题中，对于一棵子树，假设我们迁移到此题中，对于一棵子树，假设我们不购买其根结点，那么其子孙都不用讨论不购买其根结点，那么其子孙都不用讨论了由于其子孙节点都不能被购买了由于其子孙节点都不能被购买但是我们不能用加一维的方法来记录每但是我们不能用加一维的方法来记录每个附件的主件能否被购买了！个附件的主件能否被购买了！.这一结论似乎很显然，但是我们并不是要在树形构造中运用这一结论。正如上面提到的，我们要

11、在树的先根遍序上进展动态规划，而这一结论正是我们胜利的关键。 .形状Fij表示在遍历序列中从第i个物品到第n个物品，最多破费j元，能得到的最大权值和。算法算法4主件主件1附件附件主件主件2附件附件附件附件主件主件3附件附件附件附件附件附件附件附件没有购买根结点！没有购买根结点！直接直接“跳过去！跳过去！.形状总数形状总数 O(NM)形状转移代价形状转移代价O(1)时间复杂度时间复杂度 O(NM)重新组织数据后，我们再一次优解此题。重新组织数据后，我们再一次优解此题。算法算法4这样，实践上我们避开了这样，实践上我们避开了“记录主件形状记录主件形状的问题！胜利地实现了形状的合法转移的问题！胜利地实

12、现了形状的合法转移.小结小结树形构造树形构造树形动态规划树形动态规划O(NM2)线形构造线形构造合理地组织数据合理地组织数据线形动态规划线形动态规划O(NM).【题意描画】给出一棵有N个节点的有根树根为1号节点，每个节点有权值。要求对于每一个节点，求：1.其子树中权值比该节点大的节点总数2.树上一切比该节点大的节点总数3.从根节点到该节点途径中比该节点大的节点总数其中(1=N=105) 树的果实树的果实.问题分析问题分析树形上的统计问题！树形上的统计问题！序列上的统计问题。序列上的统计问题。.对数据的初步组织对数据的初步组织我们进展新的组织数据的尝试：利用先根遍历序将树转化我们进展新的组织数据

13、的尝试：利用先根遍历序将树转化为序列，由于这样，同一棵子树构成一个延续的区间，这为序列，由于这样，同一棵子树构成一个延续的区间，这是一个非常好的性质。是一个非常好的性质。问题转化为：在一个由整数构成的序列上，进展问题转化为：在一个由整数构成的序列上，进展N次区间讯次区间讯问。讯问一个区间中有多少元素的权值比给定的值大。问。讯问一个区间中有多少元素的权值比给定的值大。.在组织后的数据中尝试求解在组织后的数据中尝试求解我们直接在组织成序列的数据中进展统计。可以利用以我们直接在组织成序列的数据中进展统计。可以利用以有序表为元素的线段树！有序表为元素的线段树！每次统计的时间复杂度为每次统计的时间复杂度

14、为O(log22(N) 总的时间复杂度为总的时间复杂度为O(Nlog22(N) 预处置预处置归并排序归并排序O(Nlog2(N).我们重新思索转化后的问题。进一步组织数据进一步组织数据答案即是区间中的元素个数！答案即是区间中的元素个数！这是线段树和树状数组的看家身手这是线段树和树状数组的看家身手!思索一种特殊的情况：思索一种特殊的情况：当前的序列中一切元素的权值均大于给定的值。当前的序列中一切元素的权值均大于给定的值。.一个很巧妙的方法：从大到小地向线段树里面依次参与元素，边加边统计。324517667665431132451766排序排序依次插入并统计依次插入并统计32451766这样，我们的总时间复杂度为这样，我们的