POJ 2386 Lake Counting / HDU 1241 Oil Deposits

题意

在一片空地上,出现了若干水洼,对于一个有水的格子,他的八连通格子(上下左右左上左下右上右下)都可以看成和他连通形成一个大水洼。现在给你空地上水的配布,你要数出有多少个水洼。

思路

典型的“水洼问题”,利用DFS解决连通性问题是十分方便的。本题只要能够正确实现DFS就可以通过了,实现DFS的要点主要是正确地使用标记和正确的递归写法。对于DFS的实作原理不太理解的话请先思考树的先序遍历,可以参考我写的这篇文章

代码

 

HDU 3225 Flowers Placement

题意

求第k小的二分图最大匹配方案。

思路

这个题需要我们活用匈牙利算法了。首先正常地建图,运行一次匈牙利算法,这样初步得到了一种最大匹配样态。

接下来,我们使用DFS,从第一束花开始,从小到大挨个枚举这一位放什么,对于每一次枚举,首先要检查在当前已经有的匹配里面是不是这种花已经被匹配过了,如果是的话要解除这一匹配,接下来我们要把这一位在二分图中的匹配指向被枚举的那种花,如果被枚举的那种花原来是指向当前位置的,我们可以直接继续搜索,因为二分图可以继续有机会保持匹配,否则的话我们要以被枚举的那种花原来的东家为起点,进行一次增广路搜索(即匈牙利算法中的一环),如果没有搜索到增广路,说明这样下去也不可能出现最大匹配,可以剪枝了。

注意,如果增广路搜索失败,要把启动搜索之前的那些临时性修改复原,如果增广路搜索成功,那些修改就可以保留了。在增广路搜索过程中,注意不可以让增广路搜索修改当前DFS深度之前的已经固定了的节点。

当深度到达n时,就可以知道当前是一种合法的最大匹配样态,我们可以给计数器+1,当计数器到达k时,中断DFS过程,纪录回溯路径就是答案了。

这种方法可能有一些难以理解,其实只要把增广路过程给当成一种把当前的图给变成匹配了的图的一种“尝试修复”的过程就好了,如果尝试成功,说明以当前图的形态,还有机会出现最大匹配,如果尝试适失败,说明当前图的形态没有前途,不用再深入考虑了。

代码

 

HDU 1394 Minimum Inversion Number

题意

求环形数组的最小逆序数。

思路

如何求逆序对请参考hdu 1394 求循环串的最小逆序数 暴力法 线段树 归并排序3种方法(hnust_xiehonghao)

本题使用暴力方法也可以通过,但前提是需要知道一个结论:如果是0到n的排列,那么如果把第一个数放到最后,对于这个数列,逆序数是减少a[i],而增加n-1-a[i]的

代码(线段树优化方法)

 

HDU 1698 Just a Hook

题意

给出一个数列,每次操作更新一段的值使它们全部为给定值,问你历经N次操作之后,数列所有数加和是多少。

思路

典型的线段树加上懒惰标记来实现区间更新。因为好久没写线段树,拿这个题重温一下。

懒惰标记的工作原理可以参照:ZOJ 3686 A Simple Tree Problem

代码

 

HDU4738 Caocao's Bridges

题意

给出一个图,和一堆边,不保证没有重边,每一个边上携带者一个权值,现在问你能不能删去一条边,使图不再联通。可以的话删去权值最小的那条边,并且输出这个权值。

注意(坑点)

因为题意的特殊性,如果图本来就不联通,输出0.如果可以满足条件但最小的权值恰好是0,要输出1。

思路

删一个边把图裂开这种要求很明显就是找图的割边了。寻找割边是很典型的问题,应该使用tarjan算法,但是一定要注意重边对于找割边的影响(因为割边删掉后,图应该会裂开,但是如果有重边,删掉一条,还有一条,图显然不会裂开),因此我们要对原来的方法稍作修改,首先是存图的方式,我们不能漏掉任意一条边,因此一个理想的方式就是链式前向星。链式前向星有一个很好用的特性,我们在创建无向边的时候实际上是创建了两条有向边,而这两条有向边在链式前向星的容器中的编号是相邻的,也就是说对于编号i的边i^1就是这条边对应的反向边,这样我们就可以非常方便地标记这条边是不是已经走过(vis_e[i] = vis_e[i^1] = true)。tarjan部分附带了注释。

代码

 

HDU5396 / 15多校9-1 Expression

题意

给出了一个算术表达式,表达式里面只会含有加减乘三种运算。我们每一次从中选取两个数字并执行这两个数字对应的运算,运算结果放回式子中继续进行运算,直到最后只剩下了一个数。让我们求的是每一种不同的选取方式所得到的结果的和。

注意

这个题没有做好的主要原因是没有领会到题目中关于不同的选取方式的定义,注意到题目中讲到只要有一轮选取的数字不一样,就视为不同。这句话的含义中有两个信息:一是允许重复,二是要分先后

思路

最开始确实是没什么思路的,后来看了看board发现并不是特别难的题。于是尝试拆解问题,我们可以从算数式的一小段入手,以sample的1 + 4 * 6 – 8 * 3为例。

只考虑1 + 4部分,只有一种配置方法,就是(1 + 4);
考虑1 + 4 * 6部分,我们发现这一部分可以看成两种情况:1 + (4 * 6)和(1 + 4) * 6,在这里面我们已经考虑了1 + 4区段,而4 * 6区段只有一种配置。这样1 + 4 * 6这个区段就有两种配置了。
接下来考虑1 + 4 * 6 – 8区段,要想得到这个区段的全部情况,我们应该考虑:
1 + (4 * 6 – 8),1 + 4 * (6 – 8),(1 + 4) * 6 – 8,(1 + 4 * 6) – 8这些情况,其中(4 * 6 – 8)又可以看成考虑(4 * 6) – 8,4 * (6 – 8)这两种情况,而(1 + 4 * 6)的对应情况我们先前已经算好了。
最后,考虑1 + 4 * 6 – 8 * 3,顺着上面的思路来,就可以拆分成:
1 + (4 * 6 – 8 * 3),1 + 4 * (6 – 8 * 3),(1 + 4) * 6 – (8 * 3),(1 + 4 * 6) – 8 * 3,(1 + 4 * 6 – 8) * 3,接下来再去拆分这五种情况中的子情况。。。

如果比较敏感的话应该已经发现这就是典型的区间dp了,在推方程的时候,我们是将所有子情况的答案累加,得到当前情况的答案,但这还不够,还要注意每种情况,因为选择顺序的关系,会有多重副本,而这个副本的数量其实蛮好求,就是阶乘,而还要注意,我们在讨论当前情况的时候,是将整个等待处理的算式区段分成了(左区段)算子(分界点)算子(右区段)这样看待的,那么先后的问题又来了,我们不光左右区段的答案自身要乘上阶乘,最后整个结果还要乘上一个组合数,因为左右区段的操作又是分先后的。

以下引自官方题解,注意第2段第2行的dp[l][r]实际上是dp[l][k]

 

QQ20150820-1@2x

代码

测试数据

 

HDU 3669 Cross the Wall

题意

 

思路

需要一定的转化的斜率优化DP。

代码

 

HDU 2829 Lawrence

题意

本题和HDU 3507 Print Article如出一辙。都是给出了一个数列,和一个费用公式,要你设计一种把数列分为若干组之后计算出的总费用达到最小的方案。

思路

依然是斜率优化DP。不过本题有两个要点必须注意:1.我们默认炸毁了某一道路之后,就不要再去管默许炸毁了的道路之前的节点了。2.一定要注意DP数组的正确初始化(因为这个我挑通宵调试了近10小时)。

详细的状态转移方程还是建议自己推导,因为下标等微妙的细节稍有相左,就会产生错误,如果确信自己的方程没有问题不妨从上面几个要点调试。如果没有掌握斜率优化DP的基本知识,请移步HDU 3507 Print Article并仔细阅读教程。

代码

 

HDU 3507 Print Article

题意

给出了一个费用计算公式,现在要你把一个数列分成若干组,每一组分别套用给出的费用计算公式计算费用。你要设计一种方法使得总费用最小。

思路

本题的DP方程推导相对容易(不过我学艺不精被卡在了这一步),之后我们会发现导出的方程完全无法满足时间限制,这个时候通过对费用公式的变形可以导出一种适用于斜率优化DP的形式。

斜率优化的操作非常复杂,幸运的是已经有人写出了详实的教程:斜率优化DP。这篇教程基本是斜率优化教程中最好理解的了,并且以这个题为例题。建议学习时手动模拟操作过程,以便形象、深入地理解。

代码

实现斜率优化的要点:1.合理正确地推导出斜率的表示形式和所有的转移方程、决策判定条件。2.正确地选择大于小于号。3.单调队列的实现,同时注意单调队列无法使用STL很好地实现,只能数组模拟。4.正确地初始化DP数组(非常重要)。

 

HDU 4313 Matrix

题意

给你一颗树,上面有黑点(母体机器人所在位置),有白点(没有潜伏母体机器人的安全节点),并且给了你每一条边的边权(删边(炸毁道路)需要的时间代价)。现在要你以最小代价删掉一些边,使得没有两个黑点同时可以互相连通。输出这个时间花费即可。

思路

树形DP。这个题和Codeforces 461B Appleman and Tree是一个路子的题,都是在一棵树上不允许同时出现两个联通的特定类别的节点。这种问题我们在思考的时候,方向是将当前的大问题分解成同样的小问题,不断分解到最后,然后考虑怎么样根据一些小问题解得出大问题的解,这是DP的思路所在。

这次,我们设状态表示为dp[a][0/1],其中dp[a][0]表示要想让以a为根节点的子树满足题目的要求,而且a所在的联通块里面不可以有黑点,需要的最小代价是多少;dp[a][1]表示要想让以a为根节点的子树满足题目要求,且a所在的联通块里面有且只有一个黑点,需要的最小代价是多少。

设好了状态,我们开始想DP方程:

  • 我们当前检查的点标号是a,我们去逐一检查他的孩子节点,标号是b_{i},如果a是一个黑点:
    • dp[a][1] = \sum\min \left\{\begin{matrix}dp[b_{i}][0]\\ dp[b_{i}][0]+cost(a \rightarrow b_{i})\\ dp[b_{i}][1]+cost(a \rightarrow b_{i})\end{matrix}\right.
      因为当前节点是黑点,我们有三种操作可以选:

      • 当前讨论的孩子部分,如果他没有与任何黑点连着,我们可以把这个部分连入当前讨论的根部分,这就是dp[b_{i}][0],即孩子的代价就是根的代价,因为没有切断就没有增加代价。
      • 把根部分和当前讨论的孩子部分中间的边切断,这样的话无论孩子部分到底有没有和黑点连接,都没有关系,只要把孩子的代价加上切断代价就是这样做的代价了,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。
      • 比较这三种选择,取最优就是局部最优解了。
    • dp[a][0]=\inf
      黑点不可能不和黑点相连,所以这里用inf屏蔽掉这种选择。
  • 如果a是一个白点:
    • dp[a][1] = \min \left\{\begin{matrix}dp[a][0]+dp[b_{i}][1]\\ dp[a][1]+dp[b_{i}][0]\\ dp[a][1]+dp[b_{i}][1]+cost(a\rightarrow b_{i})\\ dp[a][1]+dp[b_{i}][0]+cost(a\rightarrow b_{i})\end{matrix}\right.
      因为当前节点是白色,我们想要让他变成连着黑色的情况,这样的话有四种操作可以选:

      • 假如截止目前和根部连接的所有孩子都不包含黑点,我们可以让现在的这个孩子部分以含有黑点的形态和根部连接,使根部变成有黑点的情况。这就是dp[a][0]+dp[b_{i}][1]
      • 假如当前的根部已经连有黑点,为了满足要求,新联入的部分不可以再包含黑点,这就是dp[a][1]+dp[b_{i}][0].
      • 假如孩子部分被切断,这样的话就无所谓孩子长成啥样了,只要算一下代价就可以了,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。
      • 这四种选择里面选最优的就好了。
    • dp[a][0] = \sum\min \left\{\begin{matrix}dp[b_{i}][0]\\ dp[b_{i}][0]+cost(a \rightarrow b_{i})\\ dp[b_{i}][1]+cost(a \rightarrow b_{i})\end{matrix}\right.
      当前节点是白色,我们想要让她不要根任何黑色连上,这样的话有3种选择:

      • 当前讨论的孩子部分没有和黑色连着,我们可以放心的把这部分连到根部,这就是dp[b_{i}][0]
      • 切断了和孩子部分之间的连接,也就是 dp[b_{i}][0]+cost(a \rightarrow b_{i})(孩子部分没有和黑点相连的情况下切断)和dp[b_{i}][1]+cost(a \rightarrow b_{i})(孩子部分有和黑点相连的情况下切断)。(其实我已经复制了这一段两遍。。。)
    • 注意这两个dp[a][0]dp[a][1]要同时处理,因为这里面有一个从“刚才”dp[a][0]到“现在”dp[a][1]的转移。

方程想好之后,DFS深入叶子部分,在返回的时候处理好dp数组就可以了,最后我们要在dp[0][0]dp[0][1]之间取个最小的,因为你所制定的根在最优解的时候连不连黑点并不知道。

代码

 

Scroll to top