算法：poj 1655 Balancing Act（树形dp）

2017年02月05日 52 阅读

算法：poj 1655 Balancing Act（树形dp）2014-01-01 csdn shuangde800题意一n个节点的棵树，去掉某个节点后，会变成一个森林.这个森林中的每个树都有个节点数量， 其中最大节点数设为max问删除某个节点后，max最小可以多少？思路和poj-3107 GodFather完全一样！ 不想吐槽了。。。其实本来不想发这篇，不过发现今天是八月最后一天，而且 还差一篇就发了80篇了。。于是。。就很邪恶的水了代码/**=====...

算法：poj 1947 Rebuilding Roads （树形背包dp）

2017年02月05日 54 阅读

算法：poj 1947 Rebuilding Roads （树形背包dp）2014-01-01 csdn shuangde800题意给一棵树,问最少删掉几条边.使得剩下的子树中有节点个数为p个的思路几天前就看了 这题, 但是没什么想法,之后每天都有去想一下, 直到今天, 在我对自己方法还有怀疑的情况下,竟然AC了 ..f（i, j） 表示子树i,保留j个节点的最少删边次数, 注意,这里保留的j个节点的子树,是指根节点为i的且有j个节点的子树.这样理解的话,...

算法：poj 2378 Tree Cutting（树形dp）

2017年02月05日 56 阅读

算法：poj 2378 Tree Cutting（树形dp）2014-01-01 csdn shuangde800题意给一颗n个结点的树，节点编号为1~n，把删除一个节点之后，剩下的分支中节点数量最多的数 量不大于总数量一半的编号全部按顺序输出思路和poj-3107 GodFather完全一样，只是输出不一样。 改为<=n/2的就输出即可。代码/**===================================================...

算法：poj 2486 Apple Tree （树形背包dp）

2017年02月05日 57 阅读

算法：poj 2486 Apple Tree （树形背包dp）2014-01-01 csdn shuangde800题意给一个n个节点的树，节点编号为1~n, 根节点为1, 每个节点有一个权值。从根节点出发，走不超过k步，问最多可以获取多少权值？思路因为和uva-1407 caves有点相似,所以没想很久就AC了，但因为初始化问题WA了两次f（i, j, 0）: 表示子树i，走j次，最终不用回到i点获取的最大总权值f（i, j, 1）: 表示子树i，走j次...

算法：poj 3107 Godfather（树形dp）

2017年02月05日 58 阅读

算法：poj 3107 Godfather（树形dp）2014-01-01 csdn shuangde800题意给一颗n个结点的树，节点编号为1~n，问删除一个节点之后，让剩下的分支中节点数量最多的尽量少。可能有多种方案，按编号顺序输出。思路简单的树形dp. 其实连dp都不能算吧...就是直接计数统计先dfs计算每个节点子树的节点个数tot[i]。再次dfs更新答案：f[i] = max（ n-tot[i], max{tot[v] | v是i的儿子} ）;...

算法：poj 3140 Contestants Division（树形dp？ dfs计数+枚举）

2017年02月05日 53 阅读

算法：poj 3140 Contestants Division（树形dp？ dfs计数+枚举）2014-01-01 csdn shuangde800题目给n个节点的带权树，删掉其中一边，就会变成两颗子树，求删去某条边使得这这两颗子树的 权值之差的绝对值最小。思路直接dfs一次，计算所有子树的权值总和tot[i]如果删掉一条边 （v, fa），fa是v的父亲节点，那么v子树权值总和为tot[v]，显然另一棵子树的权值总和就是sum-tot[v] ，最总取最...

算法：poj 3345 Bribing FIPA （树形背包dp | 输入坑）

2017年02月05日 52 阅读

算法：poj 3345 Bribing FIPA （树形背包dp | 输入坑）2014-01-01 csdn shuangde800题意有n个国家，你要获取m个国家的支持，获取第i个国家的支持就要给cost[i]的价钱其中有 一些国家是老大和小弟的关系，也就是说，如果你获得了某个老大国家的支持，那么这个国家的所有小弟 （包括小弟的小弟...递归下去）都会无偿免费支持你。问最少的花费可以得到m个国家的支持思路这题还是比较好想的树形dp, 不过输入有些麻烦， ...

算法：poj 4045 Power Station （树形dp）

2017年02月05日 56 阅读

算法：poj 4045 Power Station （树形dp）2014-01-01 csdn shuangde800题意n个城市节点构成的一棵树，节点i到节点j的电量损耗为 I*I*R*（i到j的路径所含边数），现 在要在某个结点上修建一个供电站，使得这个结点到所有其它节点的总损耗量最小。思路典型的树形dp可以先用一次dfs求出每一点的子树结点个数num[u]，以及每一点到它子树所有结点的总 距离f[u][0];然后再用一次dfs，推出每个结点到除去它子...

算法：ural 1018 Binary Apple Tree（树形dp | 经典）

2017年02月05日 59 阅读

算法：ural 1018 Binary Apple Tree（树形dp | 经典）2014-01-01 csdn shuangde800题意给一棵边有权值的二叉树，节点编号为1～n，1是根节点。求砍掉一些边，只保留q条边，这q条边 构成的子树的根节点要求是1，问这颗子树的最大权值是多少？思路非常经典的一道树形dp题 ，根据我目前做过的题来看，有多道都是由这题衍生出来的。f（i, j） 表示子树i，保留j个节点（注意是 节点）的最大权值。每条边的权值，把它看...

经典算法（1） 冒泡排序的三种实现

2017年02月05日 54 阅读

经典算法（1） 冒泡排序的三种实现2014-01-03 csdn MoreWindows冒泡排序是非常容易理解和实现，，以从小到大排序举例：设数组长度为N。1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。3．N=N-1，如果N不为0就重复前面二步，否则排序完成。 按照定义很容易写出代码：//冒泡排序1void BubbleSort1...

经典算法（2） 直接插入排序的三种实现

2017年02月05日 58 阅读

经典算法（2） 直接插入排序的三种实现2014-01-03 csdn MoreWindows直接插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。 设数组为a[0…n-1]。1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=12. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。3. i++并重复第二步...

经典算法（3） 希尔排序的实现

2017年02月05日 60 阅读

经典算法（3） 希尔排序的实现2014-01-03 csdn MoreWindows希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成 的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小） 时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序...

经典算法（4） 直接选择排序及交换二个数据的正确实现

2017年02月05日 59 阅读

经典算法（4） 直接选择排序及交换二个数据的正确实现2014-01-03 csdn MoreWindows直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接播放排序是将无序区 的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直 接放到有序区的最后。设数组为a[0…n-1]。1. 初始时，数组全为无序区为a[0..n-1]。令 i=02. 在无序区a[i…n-1]...

经典算法（5） 归并排序的实现

2017年02月05日 60 阅读

经典算法（5） 归并排序的实现2014-01-03 csdn MoreWindows归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一 个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的 第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接 将另一个数列的数据依次取出即可。//将有序数组a[]和b[]合并到c[]中vo...

经典算法（6） 快速排序 快速搞定

2017年02月05日 60 阅读

经典算法（6） 快速排序 快速搞定2014-01-03 csdn MoreWindows快速排序由于排序效率在同为O（N*logN）的几种排序方法中效率较高，因此经常被采用，再加上快速排序 思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个 ，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。总的说来，要直接默写 出快速排序还是有一定难度的，因为本人就自己的理解对快速排序作了下白话解释，希望...

经典算法（7） 堆与堆排序

2017年02月05日 64 阅读

经典算法（7） 堆与堆排序2014-01-03 csdn MoreWindows堆排序与快速排序，归并排序一样都是时间复杂度为O（N*logN）的几种常见排序方法。学习堆排序前，先 讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉 树。二叉堆满足二个特性：1．父结点的键值总是大于或等于（小于或等于）任何一个子节点 的键值。2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。当父结点 的键值总是大于或等于任何一个...

经典算法（8） MoreWindows白话经典算法之七大排序总结篇

2017年02月05日 61 阅读

经典算法（8） MoreWindows白话经典算法之七大排序总结篇2014-01-03 csdn MoreWindows在我的博客对冒泡排序，直接插入排序，直接选择排序，希尔排序，归并排序，快速排序和堆排序这七种 常用的排序方法进行了详细的讲解，并做成了电子书以供大家下载。下载地址为： http://download.csdn.net/detail/morewindows/4443208。有网友提议到 这本《MoreWindows白话经典算法之七大排序》电...

经典算法（9） 从归并排序到数列的逆序数对（微软笔试题）

2017年02月05日 52 阅读

经典算法（9） 从归并排序到数列的逆序数对（微软笔试题）2014-01-03 csdn MoreWindows首先来看看原题微软2010年笔试题在一个排列中，如果一对数的前后位置与大小顺序相反 ，即前面的数大于后面的数，那么它们就称为一个逆序数对。一个排列中逆序的总数就称为这个排列的逆序 数。如{2，4，3，1}中，2和1，4和3，4和1，3和1是逆序数对，因此整个数组的逆序数对个数为4，现在给定 一数组，要求统计出该数组的逆序数对个数。计算数列的逆序数对...

经典算法（10） 一道有趣的GOOGLE面试题

2017年02月05日 56 阅读

经典算法（10） 一道有趣的GOOGLE面试题2014-01-03 csdn MoreWindows最近在微博上看到一道有趣的GOOGLE面试题，见下图：文字版：一个 大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O（1）空 间和O（n）时间。这个题目要求用O（n）的时间复杂度，这意味着只能遍历数组一次。同时还要寻找重复 元素，很容易想到建立哈希表来完成，遍历数组时将每个元素映射到哈希表中，如果哈希表中已...

经典算法（11） 一道有趣的GOOGLE面试题 --【解法2】

2017年02月05日 55 阅读

经典算法（11） 一道有趣的GOOGLE面试题 --【解法2】2014-01-03 csdn MoreWindows上一篇《白话经典算法系列之十一道有趣的GOOGLE面试题》中对一道有趣的GOOGLE面试题进行了详细的讲 解，使用了类似于基数排序的做法在O（N）的时间复杂度和O（1）的空间复杂度完成了题目的要求，文章发表后 ，网友fengchaokobe在评论中给出了另一种解法，见下图。文字版：int Repeat（int *a, int n）{for（i...