-
[综合] 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
热度 -
81
热度 -
32
热度 -
14
热度 -
21
热度 -
[综合] POJ1840 Eqs(hash)
题意: 已知a1,a2,a3,a4,a5,求a1x13+a2x23+a3x33+a4x43+a5x53=0有几个解。 要点: 跟hash其实关系不大,主要是移项,求a1x13+a2x23+a3x33=a4x43+a5x33,这样只要三次循环即可,注意数组负数下标要加一个标准值。 15873...
62
热度