2003集訓(xùn)隊100道討論題number解題報告

安徽省蕪湖市第一中學(xué)許智磊輸入n，求所有可能的Cow(n)數(shù)列的總數(shù)。的空間內(nèi)計算出一一列舉所有可能的Cow(n)序列在時間上不可接受。Cow(n)C(len,max)C(n,n)S(len,max)為所有可能的C(len,max)數(shù)列的總數(shù)，則題目要求的就是S(n,n)。len=1時，S(len,max)=maxC(len,max)數(shù)列里面只有一個數(shù)c1，可以取從1到max的任何整數(shù)。當len=2S(len,max)=max*max。這時候C(len,max)數(shù)列里面只有兩個數(shù)c1,c2，c2各可以取從1max的任何整數(shù)，根據(jù)乘法原理，共有max*max種。然而當len更大的時候，S(len,max)就不是那么容易寫出來了。我們需要分析一下，C(len,max)這種數(shù)列有什么性質(zhì)，才有可能順藤摸瓜，找出對應(yīng)的S(len,max)的性質(zhì)。以下時，c3>c1≥1，故max至少是2，否則S(len,max)為0。：根據(jù)不等式II，有clen-1>clen-3>…>c(len-1)mod2。為了討論方便，我們設(shè)c0=0。也就是clen>clen-2kk≤lendiv2；clen-1>clen-(2k+1)k≤(len-1div2。于是當clen>clen-1時，clen>clen-1>clen-(2k+1)clen>clen-2k同時成立，也就是clen大于數(shù)列中其它所有的數(shù)，此時clen-1為最大的數(shù)。2：數(shù)列C(len,max)c1,c2,…,clen-k可以是某個C(len-k,max')數(shù)列，且max'≤max。3中數(shù)列且max'≤max。C1(len,max)：數(shù)列中clen<max，clen-1<max。也就是說此時數(shù)列中最大的數(shù)不超過max-1，因此它等價于C(len,max-1)。因此，C1(len,max)數(shù)列的總個數(shù)仍然是某個C(len-1,max')數(shù)列，因此其中最大的數(shù)只能是clen-2或者clen-1clen-2<clen=max，clen-1<clen=max，也就是新數(shù)列中最大數(shù)不超過max-1。所以新數(shù)列c1,c2,…,clen-1是一個C(len-1,max-1)數(shù)列。3C(len-1,max-1)c1,c2,…,clen一項clen=max得到的一定是C(len,max)數(shù)列。C3(len,max)clen-1=max≥clen=kclenclen-1c1,c2,…,clen-2仍clen-3=0。由于原數(shù)列C3(len,max)clen-3<clen=kclen-2<clen=k同時成立，所以c1,c2,…clen-2中的數(shù)一定都不超過k-1，所以c1,c2,…clen-2是一個C(len-2,k-1)數(shù)列。clen-1=maxclen=kci≤k-1<k=clen≤max=clen3中的不等式關(guān)系，而原先數(shù)列中的不等式關(guān)系已經(jīng)得到保證，故整個新數(shù)列符合條件3，又這個新數(shù)列的同，新得到的C3(len,max)數(shù)列顯然也不同。C3(len,max)S1(len,max)=S(len2,k1)（因為我們的分類涵蓋了所有的clen-1與clen的可能情況C1(len,max)C2(len,max)、C3(len,max)數(shù)列彼此之間不可能有相同的（clen-1clen進行無交叉的分類S(len,max)=S1(len,max)+S2(len,max)+S3(len,max)。S(len,max)

，當len，當len，當len2且maxS(lenmax1S(len1max1)S(len2k 可以計算出所有的S(len,max)最終得到S(n,n)即為所求的Cow(n)。度為O(n3)，而空間復(fù)雜度為O(n2)，因為只需要保存所有的n2個狀態(tài)值。計算狀態(tài)S(len,max),其中max>1時，用到了S(len2k

還是采用循環(huán)枚舉k的方法算。但事實上，

maxSk

2k1maxSk

2,k1)

Sk

2,k1)S(len2,S(len2k

1)S(len,0),S(len,1),…S(len,n)，在計算的時候我們可以用一個變量sumS(len2,k

1)max=1sum=0maxS(len,max)O(n2)，S(len,max)S(len,max-1)、S(len-1,max-1)和增多，例如Cowi<Cowi+