leodestiny-CSDN博客

原创 HDU 2467 Déjà vu IDA*

题意：一个机器内有M个开关，每个开关表示00~ 2n−12^n - 1之间的数字，并且每个每个数字的二进制表达中，有且只有三个1。一个数字Y通过M个开关得到的结果为： Y⊕X1⊕X2⊕...⊕XMY \oplus X_1 \oplus X_2\oplus ...\oplus X_M 现在给出初始的数字S，和目标的数字T，想用最小的开关个数，使S变成T，求出最小的开关数。如果不可能输出，impos

2015-03-22 17:44:48 1010

原创 BOJ 171 6th I 单调队列优化DP

题意：给出N个矩形的左下角的点(x1,y1)(x_1,y_1)、右上角的点(x2,y2)(x_2,y_2)。定义矩形A≤B A\le B ,当A.x2<B.x1A.x_2 \lt B.x_1且A.y2<B.y1A.y_2 \lt B.y_1。求出最长的矩形序列A1,A2,...,AnA_1,A_2,...,A_n，满足A1≤A2≤A3...≤AnA_1 \le A_2 \le A_3 ... \

2015-03-22 17:07:32 748

原创用栈将递归转化为非递归

在竞赛中如果系统栈很小的话，过深的递归会让栈溢出，这个时候我们就要自己手写栈，将递归转化成手工栈。方法其实也很简单。基本思路上，我们就是用栈不断的pop,push。但是何时push，何时pop呢？在《算法导论》上对深度优先遍历树的讲解中，在深度遍历中，会对每个节点进行染色，白色为没有被访问过；灰色为被访问过，但是该节点的所有子树还没有完成访问；黑色，节点被访问过，而且该节点的所有子树都被

2015-03-16 08:40:05 3953

原创 UVAL 3486 Cells DFS时间戳

题意：给出一颗树。有N个询问，每个询问有两个节点，判断前面的节点是否是后面节点的祖先。思路：首先要注意到题目中最后树总节点的个数上限为20000000，而对时限是3s，所以算法的复杂度基本上确定为线性。起初想的是用离线的Tarjan的LCA算法，直接求出两点的LCA，判断LCA是否和前面一个节点相等。然后RE了。最后仔细考虑，觉得应该是递归爆栈了，转换了写人工栈，时间变成了TLE，说明这个算

2015-03-16 08:20:58 1095

原创四边形不等式优化DP

四边形不等式作为一种优化手段，可以加速某一些的动态规划转移。其主要思想是利用决策变量的单调性，来减少状态转移过程中的决策，从而降低时间复杂度。其中动态规划的转移方程会有如下的特征：一.dp状态为二维，或者说可以表示成区间。一般常见的形式为：dp[i][j]=min(dp[i][k]+w[k+1][j]),1≤k<j dp[i][j] = min (dp[i][k] + w[k+1]

2015-02-26 23:45:26 727

原创 POJ 1160 Post Office 四边形不等式优化DP

题意：在一条直线上有N个城市，给出每个城市到原点的距离。现在在一些城市设M个邮局，使每个城市到邮局的距离之和最小。思路：首先要知道的是，如果N个城市设立一个邮局，邮局要位于中间（奇数为中间的一个，偶数位中间两个的任意一个）的城市上，才能使每个城市到邮局的距离之和最小。设w[i][j] w[i][j]为在第i个城市到第j个城市之间修建一个邮局，i-j之间的所有城市都使用这个邮局的最小距离和。

2015-02-26 22:11:23 749

原创斜率优化DP

当DP的时间复杂度大于时限的时候，我们就要对DP进行优化。其中一个比较常用的就是用单调队列优化DP。单调队列优化DP的思想是：减小最优解的搜索空间，提高状态转移的效率。和搜索中的剪枝一样。单调队列通过下面的操作来缩小最优解的空间： 1.队首元素保留最优解。不是最优解的队首元素需要被删除。 2.整个队列保持单调性或者是下凸性。新加入的元素如果破坏这条性质，需要从尾部把旧元素删除，直到该性质

2015-02-25 20:27:57 617

原创 HDU 3045 Picnic Cows 斜率优化DP

题意：John要组织N头牛去春游。每头牛有自己的高兴值。John需要把这些牛分成若干组，每组内至少有T头牛。每个牛的高兴值，都会降低为组内高兴值最小的牛的高兴值。John想最小化减少的值。思路：首先考虑到，对于每一组，我们要知道组内最小值、组内所有牛的高兴值、组内牛的数量，就能求出该组降低的高兴值。同时，因为牛的分配有无序性，我们可以先排序，这样最小值就可以非常容易的知道了。定义sum[

2015-02-25 17:59:22 571

原创 HDU 2829 Lawrence 斜率优化DP

题意：敌人有一条直线形状的铁路，上面有N个据点，每个据点有对应的值表示他的价值。据点之间通过铁路相连。整条铁路上的战略价值定义为:∑ (i,j) 1≤i<j≤N a i a j , \sum_{(i,j)}^{1 \le i\lt j \le N}a_ia_j,,其中(i,j) (i,j)表示可以通过铁路相互到达的两个据点，a i ,a j a_i,a_j为对应据点的价值。我们现在能炸毁据

2015-02-25 17:13:46 468

原创 HDU 3480 Division 斜率优化DP

题意：现在有N个元素的集合S。把集合S划分成M个子集，每个子集的花费为集合中最大和最小元素的差的平方。求如何划分，才能总的代价最小。思路：首先要注意到，因为集合中的元素具有无序性，我们只需知道集合中最大和最小的元素就能算出代价，也能把集合划分出来。所以，我们把所有元素进行排序，这样，最小的元素和最大的元素的位置就是已知的了。定义：dp[i][j]将前j个元素划分成i个子集得到的最小花

2015-02-25 16:01:41 562

原创 HDU 3507 Print Article 斜率优化DP

题意：Zero有一台老式打印机。他想打印一篇有N个单词的文章，每个单词有花费C i C_i。在这台打印机上一行打印k个单词的花费为(∑ k i=1 C i ) 2 +M (\sum_{i=1}^{k} C_i)^2 + M,其中M为定值。求出Zero打印这篇文章的最小花费。思路：可以注意到这个问题有重叠子问题和最优子问题。所以我们考虑从动态规划的角度来解决这个问题。定义dp[i]为打印前i

2015-02-24 10:47:36 452

原创 HDU 3586 Information Disturbing 二分+树形DP

题意：有一个信息传输网，根结点是司令，叶子节点是前线的士兵，中间的节点是各级军官，每个士兵或军官，有且只有一名直接上司，这样就形成了一个树形结构。士兵或军官只向自己的直接上司报告情报，他们通过电话线进行通话。现在，敌人想切断一些电话线，让司令得不到任何前线士兵发来的情报。切断每根电话线有不同花费w i w_i，当工具的能力大于等于w i w_i时，才能切断这个电话线。工具也有使用寿命，切断的所有

2015-02-22 13:30:32 492

原创 POJ 2486 Apple Tree 树形DP

题意：一个小女孩到了一颗苹果树上。苹果树上每个节点都有不同数量的苹果。现在小女孩从根结点出发，最多走K步，问最多可以吃到多少苹果？思路：树形DP，和前面一道题同样的思路。定义dp[u][j][1]为从节点u出发，在以u为根的子树中行走了j步，最终留在了子树中。 dp[u][j][0]为从节点u出发，在以u为根的子树中行走了j步，最终没有留在子树中。下面考虑状态转移： 1.对于dp[u

2015-02-22 11:25:39 530

原创 HDU 4003 Find Metal Mineral 树形DP

题意：人类在火星上发现一个金属矿。金属矿的道路是个树形的。在每个叶子节点有矿。现在从根结点S派出K个机器人，去取所有叶子节点的矿，希望所有机器人走的距离之和最短。思路：通过模拟可以发现，影响状态的是，有几个机器人最终留在了以u为根的子树中。所以，定义状态dp[u][j]为以u为根的子树，最终有j个机器人留在了该子树中，所有机器人走的距离之和的最小值。下面考虑状态转移： 1.没有机器人留

2015-02-22 10:37:21 492

原创 POJ 1947 Rebuliding Roads 树形DP

题意：给出一棵树，问至少删除几条边，才能出现大小为P的子树。思路：删边类型的树形DP。为了保持连通性，我们定义状态dp[u][j]为以u为根的子树，节点u必须选，得到大小为j的子树所删除的最少的边。因为无法直接将删边的信息汇总到根节点上，我们最后枚举节点，求出最后的值。下面考虑状态转移：对于节点u的儿子节点v,我们有两种选择： 1.不删除u,v之间的边，这个时候 dp[u][j]

2015-02-22 10:00:39 518

原创 POJ 1155 TELE 树形背包

题意：在一个有向树形网络中，内部节点是信息发射台，叶子节点是收听观众。根节点向儿子节点发送信息需要不同的费用。观众收听对应的信息会支付不同的报酬。现在公司想，在收益非负的情况下，让最多的听众收听到比赛信息，问最多可以收听多少听众。思路：树形DP。首先，我们可以注意到，题目中给出了N的范围，这启发我们要以N的范围作为DP的下标。定义状态dp[u][j]为以u为根的子树，让j个听众收听广播所

2015-02-22 07:55:36 544

原创 POJ 3162 Walking Race 树形DP

题意：wc建立了一个体育中心，共有N个检查点，这些检查点形成了一个树的形状。第i天，为了锻炼体质，wc从编号为i的节点出发，走到距离第i个点的最远的点。wc有一个仪器可以分析他连续几天的运动情况，但是被分析的这几天的距离的最大值和最小值的差不能超过M。请问这个仪器最长能够分析几天的结果。思路：第一问就是求出树上每个点的最长路径，这个就可以通过DFS得到。第二问是求出最长的连续序列，使序列

2015-02-22 07:29:26 551

原创 POJ 2152 Fire 很难的树形DP

题意：有N个城市，连接这些城市的道路组成了一个树形的结构。现在想在一些城市建立消防站。如果选择在城市i建立消防站，需要的费用是w i w_i，这个消防站负责该城市的防火工作。如果不选择建立消防站，那在距离为d i d_i的范围内要有一个消防站来负责城市i的防火工作。现在想让所有城市都能保证安全，求最小的费用。思路：想了很长时间，以为和前面的独立集是相关的，但是怎么也想不出来。。就去搜题解了。

2015-02-15 17:28:23 1067

原创 HDU 2196 Computer 树上最长距离

题意：一个树形的网络传输结构，求出每个节点的最远距离。思路：首先有一个结论：树上任意一个节点的最远距离对应的节点，一定是树的直径的两个端点之一。证明如下：设树的直径的两个端点为u,v，设任意一点为w。 1.当w位于u→v u\to v的路径上时，w的最远距离对应的点显然是点u或者是点v. 2.当w不在u→v u\to v的路径上时，我们利用反证法来证明上面的结论。假设w的最远

2015-02-15 16:24:51 634

原创 HDU 1520 Anniversary party 树上最大权独立集

题意：给出一颗树，树上每个点都有一个权值，求出最大权独立集。思路：和前面的和一样，我们首先将无根树转化成有根树。设dp[u][0]为不选择节点u，以u为根的子树的最大权独立集。dp[u][1]为选择节点u，得到的以u为根的子树的最大独立集。因为对于节点u，我们有可以选也可以不选。所以: 1.选择节点u后，u的所有儿子是不能选的，则： dp[u][1]=value[u]+∑ v∈s

2015-02-15 15:46:35 1096

原创 POJ 3342 Party at Hali-Bula 树形DP 最大独立集

题意：一个公司想举办聚会，但是为了气氛，如果邀请一个员工的话，是不会再邀请他的直接上司。这个公司的人员结构是树形的，每个人至多有一名直接上司。给出这个公司的人员结构，求出能参加聚会的人数的最大值，同时判断方案是否唯一。思路：同样的树的最大独立集，不同的是还需要判断方案是否唯一。其实，如果我们求出了方案数，就可以知道方案是否是唯一的。题目中是给出的每个人的名字，直接用map离散一下就可以得到数

2015-02-12 17:38:14 582

原创 ZOJ 3201 Tree of Tree 树形DP

题意：给出一棵树，每个节点有对应的权值。求出节点个数为K，且权值和最大的子树。思路：首先要解决的问题就是连通性。因为题目中，是让我们求出权值和最大的子树，如果在计算的过程中，无法保证是选取的点是相连的，那最终的答案也不是符合题意的。解决方法是正确定义DP状态。设dp[u][i][j]为选取以u为根，考虑前i个儿子节点，节点个数为j的子树的最大权值和。既然以u为根结点，那么状态转移就是从u

2015-02-12 16:54:57 547

原创 ZOJ 1134 Strategic Game 树的最大独立集

题意：给出一棵树，现在要在某些节点上放置士兵，使这些士兵能够监视每条边。最少需要放多少个士兵。思路：在图论术语上，题目所求的最少士兵的个数叫做最小点覆盖，即选择最小数量的点，使每条边都以这些点中的一个点为端点。然后有公式：最小点覆盖 + 最大独立集 = 图中点的个数。我们就将原问题转化成了求树上点的最大独立集。设dp[u]为选择以u为根的子树得到的最大独立集的节点个数。则，对于节

2015-02-12 16:21:31 530

原创 SGU 134 Centriod 树的重心

题意：给出一个树，求出所有的节点，使删除该点后，得到的最大的子树的节点个数最小。思路：上面就是树的重心的定义了。首先，我们将无根树转化成有根树。因为是要删除一个节点，我们可以枚举删除那个节点。这样对于一个节点u，我们考虑将其删除后的影响。 1.u的子节点都分别独立成一棵树，节点数最多的树就是该点的所有子树节点的最大值。 2.它的父亲节点独立成一棵树，节点数是总的节点数减去以u为根

2015-02-12 16:01:09 790

原创 POJ 1849 Two 树的直径

题意：一个城镇的道路是树形的，每条道路有对应的长度。因为下雪，每条道路都被雪覆盖了。现在有两个人从给定的点S出发，分别驾驶扫雪车去扫雪。问题是：在将所有的道路上积雪全部清理的情况下，最小化两人走过的路程。两个人没有必要回到起始点S。思路：通过手算可以发现，扫雪的过程中，有一些路会走两遍，有一些路会走一遍。两遍是因为我们要回到原来的节点，向另外一个子节点继续进行扫雪。所以，为了能够最小化走过

2015-02-12 15:48:18 660

原创 UVA 1347 Tour 双调旅行商

题意：平面上有N个点。一个人要从左上角的点向右走，到右下角的点，然后再回到左上角的点。现在想让这个人每个点到达一次，且走的总路程的距离最小。求出最小的距离。思路：双调旅行商问题。因为起点和中途点已知，我们可以把这个问题转化成两个人从左上角出发，分别不重复的到达其他点，最后在右下角的点汇合。可以注意到，在这个过程中，两个人位于的点，他们经过的点，这三个就可以描述他们的状态。

2015-02-10 00:03:38 604

原创 CF 161D Distance in Tree 树形DP

题意：给出一个无根树，统计有多少节点对之前的距离恰好等于K。相邻节点间的距离为1. 思路：树形DP。我们可以将无根树转化成有根树，这个很容易做到。对于一个子树，其根结点为s，我们只需统计s的子树之间距离为K节点对即可。然后对每个子树都进行相同的统计，就可以得到最终的答案。因为这些节点对是经过根结点s，所以他们和根结点的距离之和就是K。所以我们要知道在以s为根的子

2015-02-09 23:33:45 1715

原创 CF 245H Queries for Number of Palindromes

题意：给出长度不超过50000的字符串，询问区间[l,r] [l,r]内有多少回文子串。思路：因为字符串长度比较长，首先我们要解决的就是判断s l ...s r s_l...s_r是不是回文字符串。这个可以递推得到。设p[l][r]为起始位置为l，结束位置为r的子串是否是回文串。1表示是，0表示不是递推方程为： p[l][r]=1⟺p[l 1][r−1]=1∧s

2015-02-09 23:15:48 626

原创 POJ 2533 Longest Ordered Subsequence

题意:长度为N的序列a，求出最长上升子序列。思路：两种基本思路，都是利用的动态规划的思想第一种方法：设dp[i]为以数字a i a_i结束的最长上升子序列的长度。则有如下的转移方程： dp[i]=max(dp[j]+1),1≤j<i,a j <a i . dp[i] = max(dp[j]+1), 1\le j\lt i, a_j\lt a_i.

2015-02-09 22:23:19 394

原创多重背包的两种求解形式

1.将多重背包转化成01背包求解。即将物品的数量M按照二进制分解成 M = 1 + 2 + 4 + ... + 2 ^ k + a. 然后对这些物品进行01背包。如果没有求具体方案的，我们可以在求解的过程中进行分解，而不保留对应的物品。具体代码如下： for(int i = 0; i < N; ++i){ int num = m[i];

2015-02-05 09:49:55 981 1

原创 ZOJ Cookie Choice 多重背包单调队列优化分组背包泛化物品求和

题意：一个人想买甜点。有N种不同的甜点，每种甜点有价值Ei,价格Pi。这个人对每种甜点想买Ki块。当Ki =0时，该甜点可以买无限块。同时，因为有些甜点的味道相同，他将有些甜点分成了G组。每组内的甜点，最多买一种。现在他有D元钱，想把这些钱全花光，而且最后得到的价值最大且非负，问是否有对应的方案，如果有，求出最大的价值。思路：不同类型的背包的

2015-02-05 09:30:28 602

原创 POJ 2392 Space Elevator 多重背包

题意：牛们想造一个尽可能高的塔。他们有N种方块，每种方块高h_i,有c_i个，但是这种方块只能在高度小于a_i时使用。问这个塔最高可以搭起到多高的高度。思路：没有高度限制的话，其实把所有的方块都用上，才是最高的高度。但是有了高度a_i限制后，就变成了容量限制的多重背包。可以注意到，方块还要考虑摆放的顺序问题，不同的摆放顺序也会让塔的高度不一样。这样，我们就想能否按照高

2015-02-05 09:12:11 481

原创 POJ 1014 Dividing 多重背包

题意：有6种不同价值的石头，告诉你每种石头的数量。现在两个人要平分这些石头，希望每个人得到的价值相同的。问是否可以达到要求的方案。思路：标准的多重背包，因为找到是否存在解，把数量二进制分解就行了。代码如下：#include #include #include using namespace std;const int MAX = 200010;int a[MAX],dp

2015-02-05 09:00:42 493

原创 POJ Euro Efficiency 完全背包

题意：给出你6种货币的面值。让你求出，对于1-100中每个价值，至少需要多少枚硬币才能得到。对于价值i，需要的硬币定义为给出和收到的硬币的数量和。思路：因为需要的硬币包括给出和找零回来的钱，所以我们进行两边完全背包。注意：需要非常注意的一点是背包的容量。虽然最后的结果只是在1-100范围内，但是背包的容量是2000。因为99的硬币可以重复20次。代码如下：#include #in

2015-02-05 08:35:41 655

原创 POJ 1384 Piggy-Bank 完全背包

题意：给出储钱罐初始的重量，放入钱后的重量。给出N种货币，货币的价值和重量。问储钱罐中钱的最少的价值是多少。思路：因为钱的数量可以认为是无限的，所以是个完全背包。注意：注意初始化。代码如下：#include #include #include using namespace std;const int MAX = 50000;int dp[MAX],w[MAX],v

2015-02-05 08:28:07 479

原创 POJ 2063 Investment 变形的完全背包

题意：John有X元钱。现在有D种理财产品，给出每种理财产品的价格（1000的整数倍），每年得到的回报。现在John想投资N年，问得到的最大回报是多少。思路：一件物品可以买无限次，这是个标准的完全背包。因为每年得到的回报可以作为下一年的资金，所以这里要发生变化的是背包的容量。代码如下：#include #include #include using namespace std;

2015-02-05 08:21:09 813

原创枚举子集

对于一个用位来表示的集合，我们可以枚举其子集。设集合为sup,枚举的子集为sub按照递增的顺序枚举的话，如果只是简单的（sub+1）&sup的话,会出现前后没有发生变化的问题。应该用下面的形式：for(int sub = 0; sub != sup; sub = (sub - sup) & sup)具体原因:应该是利用了补码的不对称性，但是我好想解释不清楚。。。按照递减的顺序枚举的

2015-02-03 16:49:52 1650

原创 HDU 4281 Judges' response 状态压缩 01背包 MTSP

题意：比赛上，有N个选手提出了问题，解决每个选手的问题需要的时间是Ci。现在每个裁判至多能为选手解答时间长为M的问题。至少需要几个裁判才能解决所有的选手的问题。同时，给出每个选手的位置坐标xi,yi.希望所有裁判从起始点出发，解决完所有问题，再回到起始点，所走的距离和最小。思路：其实这两问的答案是基本没有关系。唯一的关系，就是如果第一问没有解的话，第二问也是没有解的。

2015-02-03 14:31:27 774

原创 HDU 3466 Proud Merchants 01背包单机调度问题

题意：在一个国家里，有N件商品。每件商品有价格Pi,价值Vi，和一个神奇的属性Qi。Qi表示，当你的钱大于等于Qi的时候，才能买商品i。现在你有M元钱，希望你最大化买到的东西的价值和。思路：当没有属性Qi的时候，就是个标准的01背包。当Qi被引入的时候，会发生什么变化呢？对于状态转移方程, dp[j] = max(dp[j],dp[j-p[i]]+v[i]).当没有Q

2015-02-03 09:27:47 585

原创 SGU 259 Printed PR 贪心单机调度问题

题意：有N份传单需要打印和送达。打印的时间是T，送达的时间是L。现在只有一台机器进行打印，有无限的人去送传单。问至少需要多长时间，才能将所有传单打印并送达完成。思路：简单的单机调度问题。一般在单机调度问题中，顺序问题是需要考虑的一个问题。在直觉上，那些送达时间越长的作业应该越早处理。最终的结果的表达式为：Time = T1+T2+T3+...

2015-02-03 08:58:29 1510 1

空空如也

空空如也