国家集训队2007论文集6.何森《浅谈数据的合

四川省绵阳南山中学何森浅谈数据的合理组织引子题目越来越难——数据关系越来越复杂！对组织数据的要求越来越高！合理组织在解题中越来越重要！【题意描述】给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，一个主件最多有两个附件，附件没有下一级附件。【任务】用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。金明的预算方案【数据规模】N60M3200题目中给出的主件与附件间形成树形结构，而所有的物品间形成森林结构。为了方便起见，我们给所有的主件都加上一个“上级主件”，这样，所有的物品形成了一棵树。数据的初步组织树形动态规划算法!算法1状态F[i][j]表示给以i为根的子树，总共花费不超过j元，所能取得的最大权值和。???枚举量太大，效率不高！总花费不超过j用左儿子右兄弟表示法来表示这一棵树！时间复杂度为O(NM2)状态总数O(MN)状态转移代价O(M)N*M*M=6*108，不太理想。状态F[i][j]表示以i为根的子树总共花费j元能获得的最大权值和。我们只需要枚举给左子树分配多少钱，剩下的钱都分给右子树。我们把配套的主件和附件看成一组。这样，显然对于每一组，可能的购买方案最多只有如下五种：我们换一种数据组织方式1.附件没有附件。2.每个主件最多只有两个附件。考虑本题特殊条件：1.什么都不买2.只购买主件3.购买主件和附件14.购买主件和附件25.全购买类似经典的０-１背包问题！组织数据后，我们可以得到复杂度为O(NM)的优秀算法状态总数O(MN)状态转移代价O(1)郁闷的金明【题意描述】给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，主件可以有任意多附件，附件没有下一级附件。【任务】用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。【数据规模】N60M3200题目放宽了“一个主件最多可以有两个附件”这个限制。问题分析数据组织方式依然适用效率以物品为节点的树形结构√×以组为元素的序列×-我们需要重新组织数据！我们回想上题的数据组织方式。重新安排这些物品的顺序，使得每个附件都紧跟其主件，保证其前面的最近的主件就是它附属的主件。如下图：数据组织方案二主件1附件主件2附件附件主件3附件附件附件附件树序列状态F[i][j][k]表示从第i个物品到第n个物品，最多花费j元，k表示i物品前面的主件有没有被购买，的最大价值和。这样组织数据以后，一个附件能被购买的必要条件是“其前面的最近的主件被购买了”。算法3主件1附件主件2附件附件主件3附件附件附件附件K=0主件2没有被购买K=1主件2有被购买状态总数O(NM*2)状态转移代价O(1)时间复杂度O(NM)算法3重新组织数据后，我们再次成功地设计出了O(NM)的算法。【题意描述】给出N个物品，每个物品都有一个权值(50000)和一个价格(10000)。我们称可以直接被购买的物品为主件，称不能被直接购买的物品为附件，附件只有当其主件被购买了才能被购买，主件可以有任意多附件，可以有多级附件。很郁闷的金明【任务】用不超过M元钱，购买一些物品，使得被购买的物品的总权值最大。【数据规模】N60M3200现在的题目在原题的基础条件上不仅增加附件的个数，还出现了多级附件。问题分析这是很一般的树！一般的树形结构，我们还能不能用前面的数据组织方式呢？数据组织方式依然适用效率以物品为节点的树形结构√×以组为元素的序列×－附件紧跟其主件的序列×－说明这些数据组织方式都不合理，需要再次重新组织数据！现在我们再回过头来研究一下前面一种数据组织方式：把同在一个组的主件放在附件的前面，将树形问题转化到序列上来。而现在的问题是：树的高度增加了。组织数据方案三考虑：树的先根遍历序。仔细思考算法3的状态转移：主件1附件主件2附件附件主件3附件附件附件附件K=0迁移到本题中，对于一棵子树，如果我们不购买其根结点，那么其子孙都不必讨论了（因为其子孙节点都不能被购买）但是我们不能用加一维的方法来记录每个附件的主件是否被购买了！这一结论似乎很显然，但是我们并不是要在树形结构中运用这一结论。正如上面提到的，我们要在树的先根遍序上进行动态规划，而这一结论正是我们成功的关键。状态F[i][j]表示在遍历序列中从第i个物品到第n个物品，最多花费j元，能得到的最大权值和。算法4主件1附件主件2附件附件主件3附件附件附件附件没有购买根结点！直接“跳”过去！状态总数O(NM)状态转移代价O(1)时间复杂度O(NM)重新组织数据后，我们再一次优解此题。算法4这样，实际上我们避开了“记录主件状态”的问题！成功地实现了状态的合法转移小结树形结构树形动态规划O(NM2)线形结构合理地组织数据线形动态规划O(NM)【题意描述】给出一棵有N个节点的有根树（根为1号节点），每个节点有权值。要求对于每一个节点，求：1.其子树中权值比该节点大的节点总数2.树上所有比该节点大的节点总数3.从根节点到该节点路径中比该节点大的节点总数其中(1=N=105)树的果实√问题分析树形上的统计问题！序列上的统计问题。对数据的初步组织我们进行新的组织数据的尝试：利用先根遍历序将树转化为序列，因为这样，同一棵子树构成一个连续的区间，这是一个非常好的性质。问题转化为：在一个由整数构成的序列上，进行N次区间询问。询问一个区间中有多少元素的权值比给定的值大。在组织后的数据中尝试求解我们直接在组织成序列的数据中进行统计。可以利用以有序表为元素的线段树！每次统计的时间复杂度为O(log22(N))总的时间复杂度为O(Nlog22(N))预处理——归并排序O(Nlog2(N))我们重新考虑转化后的问题。进一步组织数据答案即是区间中的元素个数！这是线段树和树状数组的看家本领!考虑一种特殊的情况：当前的序列中所有元素的权值均大于给定的值。一个很巧妙的方法：从大到小地向线段树里面依次加入元素，边加边统计。324517667665431132451766排序依次插入并统计32451766这样，我们的总时间复杂度为O(Nlog2(N))小结树序列嵌套数据结构“从大到小”组织“形态”一般数据结构组织“顺序”以上我们从几个例题介绍了“数据的合理组织”的重要性及其在解题中的一些应用，然而例题只是一部分题目的代表，具体的题目应该具体分析。总结没有最合理的数据组织方式！多思考，多总结，多实践，才是万能的解题之道。谢谢