內(nèi)容教案成果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.基本思路從小到大，逐個(gè)嘗試可能的長度。設(shè)已知的n根短棍的長度分別是：l1,l2,ln現(xiàn)在的問題就是：要判斷這n根短棍是否可以組成m根長為length的長棍。這題和Dividing(1014)那題很像，從題意上可以把Dividing看成是此題的簡化版本。然而仔細(xì)分析這兩題有很大不同，因此解法也是大相徑庭的。Dividing那題的數(shù)據(jù)總量可以達(dá)到20000，直接的深度優(yōu)先搜索是很難奏效的，所以我們的想法是如何有效的減少數(shù)據(jù)總量。而對(duì)于此題來說，雖然我不知道實(shí)際測試數(shù)

4、據(jù)的最大的數(shù)據(jù)量（sticks的總數(shù)）是多少，但是我只用了一個(gè)長為100的數(shù)組保存也沒有越界。說明總的數(shù)據(jù)量不超過100（注：要解這題要我覺得要使用深度優(yōu)先搜索，對(duì)于深度優(yōu)先搜索來說100已經(jīng)是很大的數(shù)了）。具體思路對(duì)于這個(gè)問題，可以有2種不同的解決方法：1.逐個(gè)使用l1,l2,ln來填充長棍。2.逐個(gè)填充長棍，填完一根長棍，再填下一根。無論是哪一種解題思路，我們都可以“感覺到”如果有如下的關(guān)系成立l1=l2=ln 那么對(duì)于解題是十分有利的。事實(shí)也是如此，在此種情況下將會(huì)比較高效的排除不可能的情況。此題的實(shí)際測試結(jié)果也是如此，如果讀入數(shù)據(jù)后沒有排序，我所見過每種算法都會(huì)超時(shí)。第一種思路的程序框

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);/此步和我的第一個(gè)優(yōu)化類似 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; /此步和我的第三個(gè)優(yōu)化類似 if (sticki = length - now) return; 以上的程序段來自與lowai，運(yùn)行時(shí)間是20ms。在這段程序中也使用了一些優(yōu)化，經(jīng)過實(shí)驗(yàn)，在不加入其中任何一個(gè)優(yōu)化的情況下，計(jì)算結(jié)果都會(huì)超時(shí)。總結(jié)1.深度優(yōu)先搜索的順序