POJ 2955 Brackets

题意

给出一个由小括号喝中括号组成的括号序列,定义正规括号序列为(),[],(s),[s],其中s也是正规括号序列。求最长正规括号序列的长度。

思路

考虑区间DP,设计状态时着眼于“最后一次加括号”。

状态表示:dp[i][j] = 从 i 到 j 的(包含i,j)最长的括号序列长度。

状态转移:

  • dp[i][j] = dp[i][j-1] 继承上一个区间的结果
  • 令k为i,j之间的一个位置,str是给出的括号串(令下标从1开始)
  • 如果str[k]与str[j]正好是一对匹配的括号,可以考虑在最后一步放这个括号,用dp[i][k] + 2 + dp[k+1][j-1]尝试更新dp[i][j]

答案:dp[1][len]

初始化:直接令整个dp数组都为0,既可以完成初始化,也可以无效化所有无效状态。

代码

 

POJ 2114 Boatherds

题意

给出一棵树,树边带有边权,问你能不能找出一条路径使得路径边权之和正好等于给出的k值。

思路

和这个题非常像,只不过题意从计算有多少点对之间距离小于k换成了判断有没有一条路径等于k。但实际上可以用一套思路解决。

代码

 

POJ 1987 Distance Statistics

题意

给出一棵树,和树上两点之间的边权大小,要你快速回答出树上有多少不同的点对使的这对点之间的距离至多为k。

思路

典型的点分治问题。

当考虑一棵有根树中有多少点对的距离小于等于k时,可以求出所有节点到根部的距离,然后使用二分,或者尺取的方法得到有多少对点之间的距离小于等于k。但是在上面的计算过程中我们想要求的是经过根部的符合要求的点对数量,但实际上多算入了一些并不符合要求的点,同时也漏掉了不经过根部的符合条件的点对。

所以我们可以这样看:一棵树的符合条件点对数=上面所述方法找出的点对数-各个子树中两点间距小于等于(k-2e)的点对数目(e是根部到孩子的树边的边权)+各个子树符合条件的点对数

上面的式子是递归的,这是一个树分治(点分治)策略。

在实现树分治的时候,一定要注意只有配合了重心的点分治才能达到O(nlogn)的复杂度,否则会面临特殊情况(比如链)退化到O(n^2).

代码

 

 

POJ 3107 Godfather

题意

变相考察树的重心。

思路

请参考这个题和/或这个题

代码

 

POJ 2378 Tree Cutting

题意

变相考察求树的重心。

思路

和这个题一致

代码

 

POJ 1655 Balancing Act

题意

求树的重心。

思路

树的重心的定义是:选树中某个点i当作树的根,所有子树中最大的那棵的大小是Si,整棵树中能令Si最小的那个点,就是树的重心。

求重心是作为树分治的一个环节出现的,只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。

求重心的想法是树dp,对于每个节点都要存储他所有孩子对应的子树中最大子树的大小,还要存储他的父亲是谁。求好了这些数据之后,按着定义,就可以知道谁是重心了。

代码

 

POJ 3646 The Dragon of Loowater

题意

请参考<LRJ大礼包::白>的第一章例题1.

思路

大概是贪心。因为骑士的能力=能砍多大=花多少钱,这样的话只要排个序,从最便宜的英雄开始检查,从小头开始砍,直到检查完最后一个英雄。

如果没砍死就是没解,否则一定是最优解,这个思维和Kruskal算法是一致的。

代码

 

POJ 3278 Catch That Cow

题意

给出你一条直线,和你在直线上的位置以及牛在直线上的位置,你每一次操作可以左移一个单位,或者右移一个单位,或者把你当前的坐标直接乘2作为你的新坐标。你要求出你最少要经过多少次操作才能正好移动到牛的位置上。

思路

不典型的最短路问题数据较小时可以使用BFS解决,不过本题不能盲目DFS,要注意排除掉已经不可能产生优解/更优解的情况,在这里我剔除掉的情况是:

  • 当前走的步数已经大于等于当前最优解了
  • 当前的位置已经小于0了
  • 当前的位置与牛的距离已经超过了开始时与牛的距离(合理的最坏情况下的距离)。
  • 当超过了牛的位置时,只能选择回退,如果接下来的回退所消耗的时间加上现在已经消耗的时间已经不可能再产生更优解

上述这种在搜索途中将一些预计不能产生优解/更优解的情况排除掉的方法也称为“剪枝”,这是暴力搜索中很常用、很重要的一种优化手段。

代码

 

 

POJ 3126 Prime Path

题意

给出你两个四位素数,保证这个素数不会有前导0(也就是1003起跳)。给定一个操作,在只改变一位的前提下,把当前素数变为另一个四位素数(无前导0)。现在问你至少进行多少次这样的操作才能把一个素数变为另一个。

思路

素数的朴素判断需要O(sqrt(n))的时间复杂度,显然不符合本题要求。不妨使用欧氏筛法,在O(n)的时间复杂度内预处理出10000以内的全部素数,之后O(1)时间解决查询某个数是否为素数的问题。

解决完素数问题,剩下的就是近似于求最短路的BFS过程了。具体的实作方法可以参考下面的代码。

代码

 

POJ 3087 Shuffle'm Up

题意

你需要模拟一个洗牌过程,每一次把左右两个牌堆交叉叠放在一起,然后把整个叠放好的大牌堆再分成上下两半作为左右牌堆。现在给出你初始的左右牌堆,和一个要达到的目标大牌堆,问你至少要经过多少次洗牌,才能使左右牌堆直接叠放在一起等于大牌堆。

思路

这个题的数据还是比较小的,不妨尝试模拟洗牌过程,然后设定一个洗牌次数上界,只要在上界规定之内的次数没有洗出符合要求的牌堆,就视为无解。

代码

 

Scroll to top