集訓(xùn)隊(duì)作業(yè)fence解題報(bào)告

1、Fence 解題建立模型題目中允許每根木條最多削去m 個(gè)長度，處理起來甚是不便。先預(yù)處理：對(duì)每類木條，分別削去 0, 1, 2, , m，得到若干新的木條種類；然后將所有的木條綜合，除去重復(fù)，得到的木條種類集合記為S。不妨令n = |S|，則問題的模型可以描述為：已知：集合 S，n = |S|。 求：一個(gè)正整數(shù) p，使得：1、p 不能由 S 中的數(shù)通過加法運(yùn)算得到。2、對(duì)所有的 q p，q 均能由 S 中的數(shù)通過加法運(yùn)算得到?？梢娔Ｐ鸵雅cm 無關(guān)，其中的n p能不能由S 中的元素組成（“組成”即通過加法運(yùn)算得到）。然而這樣的 q 有無窮多個(gè)，不可能逐一判斷之，必須合理的對(duì)所有自然數(shù)進(jìn)行分類，然

2、后分而治之方是可行之法。設(shè)S 中最小的元素是u，則可以按照mod u 的值將所有自然數(shù)分成u 類。而且顯然，如果t = ku + r（r u）可以由S 中的元素組成，那么任意的t = ku + r（r k）就都可以由S 中的元素組成。如果x 滿足：x mod u = r。x 能由S 中的元素組成。x 是滿足條件(1)、(2)的最小正整數(shù)。則記f(r) = x。顯然，凡是不小于f(r)、模u 等于r 的數(shù)，都能由S 中的元素組成。接下來考慮如何求f。迭代法用迭代法求f 是十分容易想到的。第一步：賦初值。令所有的f(i) = +。對(duì)所有的 xS，如果滿足 x f(x mod u)，則更新 f(x

3、mod u) = x。第二步：迭代。任取a, b（a u, b u），使得 f(a) + f(b) f(a + b) mod u)。如果找不到則“迭代”結(jié)束，否則更新f(a + b) mod u) = f(a) + f(b)。這樣就求出了所有的f。然而迭代法的時(shí)間復(fù)雜度過高：O(n3)，實(shí)際應(yīng)用中表現(xiàn)也比較差。因此不得不考慮優(yōu)化算法。類 Dijkstra 算法上述迭代法十分類似最短路的迭代法；而問題模型本身也和最短路問題十分類似，于是我猜測(cè)是不是可以將解決最短路問題的高效算法 Dijkstra，通過一定改進(jìn)，“移植”到本題上來呢？是肯定的。 第一步：賦初值。令所有的f(i) = +。對(duì)所有的

4、xS，如果滿足 x f(x mod u)，則更新 f(x mod u) = x。同時(shí)給每個(gè)f(i)一個(gè)屬性checki :優(yōu)值。一開始所有的checki false。第二步：更新。，表示當(dāng)前的f(i)是否能確定為最1、從所有滿足 checki = false 的f(i)中選擇一個(gè)最小值，記為f(p)；如果不存在這樣的p，則結(jié)束算法。2、checkp true。3、如果q 滿足：f(p) + f(q) f(a1) + f(a2) + + f(al)其中(a1 + a2 + + al) mod u = p。顯然f(ai) = f(t + ai) mod u)。因此：f(p) f(a1) + f(a

5、2) + + f(al) = f(a1 + a2) mod u) + f(a3) + + f(al)= f(a1 + a2 + a3) mod u) + f(a4) + + f(al)= f(a1 + a2 + + al) mod u) = f(p)即f(p) f(p)，。命題得證。因此，原算法是正確的。完成f 值已然求出，余下的工作就十分簡單了。設(shè)最后的結(jié)果為x；gi = fi / u（x表示取整）；g = maxgi。顯然，凡是除以u(píng) 商為 g 的數(shù)，都能表示；故而x / u = g 1。如果某個(gè)p，滿足：1、gp = g。2、p 是滿足條件 1 的最大值。則x mod u = p。所以，

6、x = (g 1) * u + p。整個(gè)算法的時(shí)間復(fù)雜度是 O(n2)（1=n=3000）。小結(jié)此題的關(guān)鍵在于要對(duì)自然數(shù)按照mod u 的剩余類來劃分，將復(fù)雜不可解的問題簡化。另外對(duì)迭代法進(jìn)行優(yōu)化時(shí)，類比的方法也起到了重要作用。通過此題總結(jié)出一些基本經(jīng)驗(yàn)：1、化難為易、化繁為簡。2、大膽合理的聯(lián)想、類比。程序constfin = fence.in; fout = fence.out; maxn = 3000;procedure pr(x : long); 輸出 beginassign(output, fout); rewrite(output);if x = 0 then wrin(-1) e

7、lse wrin(x); close(output);halt;end;varmin :eger;f : array0 . maxn of long;procedure init; 初始化 varcheck : array-maxn . maxn of;i, j, x, n, m :begineger;assign(input, fin); reset(input);readln(n, m);fillchar(check, sizeof(check), false); for i := 1 to n do beginreadln(x);for j := x - m to x do checkj

8、 := true; end;close(input);min := 1; while not checkminnc(min);求 ufor i := 0 to min - 1 do fi := maxlong; for i := 1 to maxn doif checki and (i fi mod min) then fi mod min := i;end;f 數(shù)組賦初值procedure main; varcheck : array0 . maxn of;i, j, p :eger;tmp, minv : long; beginfillchar(check, sizeof(check), false); for i := 1 to min do beginminv := maxlong; p := -1;for j := 0 to min - 1f not checkj and (fj minv) then begin minv := fj; p := j;end;選最小的 f(p)if p = -1 then break; checkp := true;標(biāo)記for j := 0 to min - 1f fj maxlongtmp := minv + fj;then begin更新if tmp ma