内容教案成果1

1、问题描述SticksDescription George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. 解题要求1. Time Limit, Memory Limit2. In

2、put3.OutputTime Limit:5S Memory Limit:10000KInputThe input file contains blocks of 2 lines. The first line contains the number of sticks parts after cutting. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.OutputThe output file cont

3、ains the smallest possible length of original sticks, one per line.基本思路从小到大，逐个尝试可能的长度。设已知的n根短棍的长度分别是：l1,l2,ln现在的问题就是：要判断这n根短棍是否可以组成m根长为length的长棍。这题和Dividing(1014)那题很像，从题意上可以把Dividing看成是此题的简化版本。然而仔细分析这两题有很大不同，因此解法也是大相径庭的。Dividing那题的数据总量可以达到20000，直接的深度优先搜索是很难奏效的，所以我们的想法是如何有效的减少数据总量。而对于此题来说，虽然我不知道实际测试数

4、据的最大的数据量（sticks的总数）是多少，但是我只用了一个长为100的数组保存也没有越界。说明总的数据量不超过100（注：要解这题要我觉得要使用深度优先搜索，对于深度优先搜索来说100已经是很大的数了）。具体思路对于这个问题，可以有2种不同的解决方法：1.逐个使用l1,l2,ln来填充长棍。2.逐个填充长棍，填完一根长棍，再填下一根。无论是哪一种解题思路，我们都可以“感觉到”如果有如下的关系成立l1=l2=ln 那么对于解题是十分有利的。事实也是如此，在此种情况下将会比较高效的排除不可能的情况。此题的实际测试结果也是如此，如果读入数据后没有排序，我所见过每种算法都会超时。第一种思路的程序框

5、架bool solve(k)/填第k根短棍 for(i=0;im;i+)if(lk+第i根长棍已填的部分 m) ok = 1; printf(%dn, length); return; int i; for (i = 1;i = n;i+) if (!usedi) break; usedi = 1; search(x,sticki,i);/此步和我的第一个优化类似 usedi = 0;void search(int num,int now,int next) if (ok) return; if (now = length) solve(num + 1); return; for (int i = next + 1;i = n;i+) if (!usedi) if(sticki + now = len) usedi = 1;search(num,now + sticki,i);usedi = 0; if (ok) return; /此步和我的第三个优化类似 if (sticki = length - now) return; 以上的程序段来自与lowai，运行时间是20ms。在这段程序中也使用了一些优化，经过实验，在不加入其中任何一个优化的情况下，计算结果都会超时。总结1.深度优先搜索的顺序