当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] POJ1383 Labyrinth(树的直径:两次BFS)

    题意: 给一个迷宫,要求迷宫中最长的路径(就是两点之间的距离最大) 要点: 树的直径问题,有两种方法:第一种就是两次BFS:先以任意点搜索一次找到最长段的一端v,再以v搜索找到最长段的另一端w,第二次搜索出的就是最长路径。第二种就是DP,用记忆化搜索应该可以写,以后再说。 15566071...

    57
    热度
  • [综合] 例题9-12 UVa12186 Another Crisis(树型DP)

    题意: 看白书 要点: 白书上写的还是很清楚的,通过递归进行动态规划,vector还真是好用,暑假的时候学一下。 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algor...

    68
    热度
  • [综合] 例题5-4 UVa156 Ananagrams(STL:map)

    题意: 看白书 要点: 树型DP求树的最大独立集需要用到map,本来想暑假学了C++再学STL的,后来觉得还是先稍微学一下,能简单使用再说。这题就是照着书上敲了一下。不得不说,C++真是比C好用太多了。 map的使用参考:点击打开链接 #include<iostream> #incl...

    85
    热度
  • [综合] POJ1351 Number of Locks(DP:记忆化搜索)

    题意: 锁上有n个槽,槽的高度可以是1~4,现在要求锁上至少有两个相邻的槽之间的高度差为3并且至少有3种不同高度的槽,问有几种排列方式 要点: 这题应该是可以通过排列组合简单得出结论的,但是我推不出来,看了一下网上的做法都是用DP记忆化搜索,思路是用dp[i][now][j][m]存储有多少种方案,...

    44
    热度
  • [综合] POJ1065 Wooden Sticks(贪心||DP)

    题意: 一些有长度l和重量w的木棍要装在机器上,如果前一个木棍长度和重量均小于等于当前木棍,装上机器不耗时,否则时间+1,问全装上最少时间。 要点: 可以用贪心或DP,贪心就是先按长度从小到大排好,再根据重量,用一个d数组标记是否用过,从一根木棍出发,往后找重量大于等于它的木棍,将它的d标记为1,再...

    51
    热度
  • [综合] POJ2446 Chessboard(二分图)

    题意: 一个n*m的棋盘上有t个坑,要求用1*2的纸条完全覆盖这个棋盘,纸条不能盖上坑。 要点: 这题是二分图,就是求二分图的最大匹配,看是否与棋盘格子数-坑数相等。但是具体的集合很难想,看了网上题解,确实比较精妙。首先我们知道如果一个格子的行数+列数i+j是奇数,它相邻的格子的i+j必定为偶数,所...

    83
    热度
  • [综合] POJ3311 Hie with the Pie(DP:TSP问题)

    题意: 要到n个城市送披萨,每个城市只能经过一次,最后要回到原点,求最短路径。 要点: 经典的TSP问题,从0出发找到一条回路回到0,这就意味着可以回溯到前面的城市重新出发,这样就比较难。基本上可以想到先用Floyd算法求出每两个点的最短路径,然后就是DP,定义一个d[i][s]数组,表示当前在第i...

    20
    热度
  • [综合] 非递归实现二叉树的各种遍历

    逛知乎看到有人去微软面试遇到让白板写非递归的二叉树的中序遍历,自己想了一下,非递归基本上就是用栈模拟,其他还好,后序遍历比较难写。 参考博客:点击打开链接 #include<cstdio> #include<stack> #include<algorithm>...

    50
    热度
  • [综合] HDU1421 搬寝室(DP)

    题意: 中文题不解释。 要点: 要在n个中选k对,使每两个之差的平方和最小,可以用dp[i][j]来表示i个数中选了j对的最小值,以当前的第i个数来判断,如果不选这个数,说明就是前一个数的值,dp[i][j]=dp[i-1][j];如果选这个数,说明它前面的数也要被选,dp[i][j]=dp[i-2...

    32
    热度
  • [综合] 将C语言的声明翻译成通俗语言——cdecl

    《c专家编程》中的一个程序,可以将声明翻译为通俗语言,主要运用栈,挺难的,我自己是写不出的,照着书敲了一遍。 普通方法: #include<stdio.h> #include<string.h> #include<ctype.h> #include<stdl...

    29
    热度
  • [综合] POJ3616 Milking Time(DP:最大子段和)

    题意: 奶牛产奶,一共n长的时间,可以有m个时间段,每个时间段对应一个产奶量,一个时间段后要休息r时间,求最大产奶量。 要点: 就是一个最大子段和的变形,先将时间段从开始排序,可以写出状态转移方程为: if(time[i].x>=time[j].y+r) dp[i]=max(dp[j]+tim...

    70
    热度
  • [综合] POJ3181 Dollar Dayz(DP)

    题意: 将N分解为为1~K的因子,求有几种分解方法。 要点: 这题挺难,用dp[n][m]表示n分解后最大因子为m的分解方法总和。可以写出状态转移方程dp[i][j]=dp[i][j-1]+dp[i-j][j-1]+……,可以这么理解:dp[i][j]可以由最大因子为j-1的通过i减去j的整数倍来得...

    88
    热度
  • [综合] HDU1160 FatMouse's Speed(DP+路径记录)

    题意: 输入一组小鼠的体重和速度,要求输出体重从小到大而速度从大到小的数目最多的小鼠的数量和具体序号。 要点: 简单的最长上升子序列,只要先排序再DP即可,就是要记录一下路径最后递归输出就行。 17447680 2016-07-0614:10:34 Accepted 1160 0MS 17...

    71
    热度
  • [综合] POJ3267 The Cow Lexicon(DP)

    题意: 有一个字符串以及有很多单词的字典,求在字符串中删除最少的单词数,使字符串和字典中的单词完全匹配。 要点: 这题我是没想出来,看了网上大神的解题报告。重点就是用dp[i]表示从i到字符串末尾n要删除的最小数目,后面再分为能匹配和不能匹配进行状态转移。 参考博客:点击打开链接 1569...

    75
    热度
  • [综合] UVa1625 Color Length(DP)

    题意: 看白书 要点: 白书上的题,还是有些难度的,具体分析看书吧,难点就是要求res[i][j]。 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm&g...

    74
    热度
  • [综合] 堆实现最优队列

    最优队列就是靠堆实现的,普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出(largest-in,first-out)的行为特征。也就最优队列可以保证队头一定是有限度最大的元素。一个...

    81
    热度
  • [综合] 几种线性时间排序

    一般我们使用的堆排序,归并排序都是属于比较排序,也就是通过比较元素的大小来进行排序,可以通过决策树分析出比较排序的时间下界是O(nlgn),堆排序和归并排序都是渐进最优的比较排序算法。还有其他的排序方法不是通过比较,下面总结一下: 一:计数排序 大致思路是将数组中所有元素对应小于这个元素的个数存储...

    32
    热度
  • [综合] 中位数与顺序统计量

    一:最小值和最大值 在有n个元素的集合中如果想找最小值,最优也就是n-1次,但如果同时找最大值和最小值,最优可以不是2(n-1)次而是3*(n/2)次,基本思路是成对的比较,先两个数之间比较,较小值与最小值比较,较大值与最大值比较,注意奇数偶数要分开讨论。 #include<iostream...

    14
    热度
  • [综合] 散列表的初步实现

    看算法导论补了一下散列表,也就是hash表,hash表还是很好用的,兼顾了空间和时间,查找操作只要O(n/m),基本的难点在散列函数这里,全域散列这里看不太懂,初步敲了一下除法散列法和乘法散列法的实现,基本没啥好说的,看完开放寻址法以后找两道OJ题做做。 #include<iostream&...

    21
    热度
  • [综合] POJ1840 Eqs(hash)

    题意: 已知a1,a2,a3,a4,a5,求a1x13+a2x23+a3x33+a4x43+a5x53=0有几个解。 要点: 跟hash其实关系不大,主要是移项,求a1x13+a2x23+a3x33=a4x43+a5x33,这样只要三次循环即可,注意数组负数下标要加一个标准值。 15873...

    62
    热度