题目大意是一个线段分成n段涂色，有m种颜色可用，给出每种颜色的费用，每一段规定了所用的颜色以及涂色长度区间。同种颜色的涂色长度不能相同，求是否能按要求完成涂色以及最少需要花费的费用。
很典型的搜索题，主要用到了2个减枝技巧：
其中第二个预处理通过O(nl^2)的DP完成。
2353428 2010-11-19 02:08:21 Accepted 2633 C++ 1320 212 IwfWcf
题目大意是一个平面图中相邻（即在同一条边上）的两点不能用同一种颜色染色，求为给出的图染色所需的最少颜色。
先介绍一个定理--“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”，这个定理叫四色定理。基于这个定理，本题中所需的颜色数量不会超过4，因此只需用DFS判断能否用m种颜色完成染色，输出成功的m的最小值即可。
7756121 IwfWcf 1129 Accepted 388K 0MS G++ 1076B 2010-10-17 20:57:54
新年第一篇，好久没做题了，准备先拿水题练练手，不过无奈第一题就做得不是很顺，一开始没注意到m很小，想不出DP的状态转移方程，此后注意到可以用搜索又因为自己的上界估计错误（一开始估255）在第6个测试点卡了很久。
没想到什么特别好的优化，只想到一个保存上一层的递推结果，搜索到下一层时直接在此基础上递推不必全部重新推一次，但嫌增加了编码复杂度且m很小所以没有写上去。
PS：这也是Laptop上的第一篇，希望能尽快熟悉在Laptop上打字提高编码速度。
R1123556 Accepted 100 From IwfWcf－ P1179 FPC Vijos Dolphin 2009-1-26 10:25:03
题目大意是求给出的图中的割顶以及其所分割的子网数。
求割顶的方法非常简单，以对每个点的连接点作DFS一直到覆盖其所有连接点为止，达到覆盖所有连接点时所作的DFS次数就是子网数。注意本题数据中给出的图是一个非常稀疏的图，所以可以用邻接表优化空间储存效率。
3008859 2008-07-27 15:21:01 Accepted 1119 FPC 00:00.00 424K IwfWcf
题目大意是给出m条边的边长，问能否用这些边拼接成一个正方形。
貌似只能DFS。用的剪枝和优化如下：
2997030 2008-07-22 18:00:51 Accepted 1909 FPC 00:00.07 408K IwfWcf@LZOI
题目大意是给出t和n个数（递减），输出用这n个数所组成的所有不同的和为t的等式，等式要求数字自上到下，自左到右递减。
一开始看反了t和n，但除了搜索又想不到什么其他方法，再次读题的时候气了个半死……因为n最大只有12，所以用DFS的时间复杂度就是可以接受的了。剪枝只用了一个最基本的可行性剪枝，因为数列递减，所以如果sum+num[now]*(n-now+1)<t则必然不能组成合乎要求的等式。
2996883 2008-07-22 17:15:27 Accepted 1711 FPC 00:00.00 408K IwfWcf
题目大意是给出m个数，用这m个数组成加法等式（等式右边只有1个数）并按顺序（先输出长度小的，长度相同的情况下先输出从左到右数字小的）输出所有可能的等式。如果无法构成等式则输出"Can't find any equations."。
我是用DFSID来做的。先对输入数据排序，求出最大可能深度，然后限制深度进行DFS就是了，剪枝方面我只用了一个最基本的判定可行性的剪枝。
2993372 2008-07-21 13:25:03 Accepted 1204 FPC 00:00.68 412K IwfWcf@LZOI
题目大意是有100个气球供两个人踩，这一百个气球上分别标上了1-100的数字，两个人的初始得分都是1，每踩一个气球得分就乘上该气球上所标数字，给出两个人的得分，判定该得分是否有矛盾（即无法找到一种可能达到该得分，但两个人不睬到同一个分数的气球的方案）。如果有矛盾就输出得分低的人的分，否则输出得分高的人的分。
这题有DP解法，但没有思路，所以我是用DFS来做的。思路很简单，如果a小于b则交换两数，然后自2开始尝试将每个气球分给两人踩，如果b可除尽且a也可除尽则无矛盾，如b可除尽而a不可除尽则有矛盾。虽然觉得不应该出现，但如果两数都无法除尽按照题目要求我是判定无矛盾的。因为是有排名系统的在线题库，按照我的惯例代码就不公开了，有交流需要的可以联系我获得。
2993005 2008-07-21 10:49:19 Accepted 1003 FPC 00:00.07 404K IwfWcf
博文
所有评论
