-Flyぁ梦-

花了一晚上把zoj一道TLE的陈年旧题2891给A了，一个简单dfs加基于数列排序检查，算法比较简单但是代码量比较多有170行，可以算比较复杂，过了Sample和自己编的几个临界数据，想想就交了试试看吧。

提交完，居然直接看到了红色的“Acceped”（这比较奇怪，做过zoj的应该了解，提交的瞬间很多情况下是Compiling的状态），居然这尝试性的一次提交就过了，居然之前TLE10s的题现在只用了10ms，在确认没看错submit ID后，居然还发现占据了这道题AC排行榜第二而且榜单中大多都是好几秒的submit。瞬间就怀疑zoj是不是当时抽风了还是数据被换简单了 …

各种确认无误和心态调整过来后，当然就是兴奋和激动了，隔了一年不做ACM题了这一下试手这一曾经卡住并且有难度又复杂的题，一下子AC而且速度还不错这个结果的确让自己大为震惊接着喜出望外。做ACM的话，动力就来源于此吧，虽然自己做ACM并不太因为是自己的兴趣使然，而主要是为了练习算法和coding能力为了准备明年找工作。当然有一点，2891的榜单不太理想完全是因为这道题题目太长理解麻烦解题又复杂算法又不难导致众大牛不想做而已，这点自己心理还是有数的…

AC之后，真可谓思绪万千，从惊转喜后，自然想把这种喜悦分享开来，却无奈地发现可以分享此心情的朋友基本不懂ACM，除了耗子，很想与木头分享此刻的心情，但猜得到得到的回复不过是“。。。”而已，她又不懂何况即使懂也大多如此，却又何必麻烦她敲键盘呢…木有妹子的寂寞啊，虽然即使有妹子好像也不能解决此烦恼（除了ACM妹子），ACM之路注定寂寞孤独啊…

解题思路

1. 数据预处理
2. dfs得到符合题目条件的3组数据（最大化相同的每组数据和，这里没有检查连接点是否冲突）
3. 用排序的方法检查是否有存在可行的排列方案

第一步中，将数据排序然后合并重复数据，进行数据组合而不是排列。这里若不合并重复数据，Sample中第四组会花费很多时间直接TLE。然后得到可能的最大长度和最小长度，从最大开始遍历dfs。这里看似从最大Len到最小Len跨度很大每个都要重新进行一次dfs，但是很多Len的dfs因为凑不好长度dfs很快就会退出。

第二步dfs，根据木棒序号（0 1 2）、当前木棒长度（从0到最大Len）、上一根短木棒序号这3个数据进行dfs，得到一组可用的数据。这里dfs递归不会很深。

第三步，用三重循环next_permutation模拟各种短木棒的组合方法，试出可能存在的方案。这里循环虽然很多，而且每一条长木棒最多可能由9根短木棒组成，但是只要凑到一种可行的方案即return，大多数情况下进行不了几次循环的。

源代码：zoj 2891.cpp