从《Cash》谈一类分治算法的应用

【文件属性】：

文件名称：从《Cash》谈一类分治算法的应用

文件大小：69KB

文件格式：DOC

更新时间：2020-11-13 05:25:03

cdq分治,ACM

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同．求出子问题的解，就可得到原问题的解．分治算法非常基础，但是分治的思想却非常重要，本文将从今年NOI的一道动态规划问题Cash开始谈如何利用分治思想来解决一类与维护决策有关的问题：