小木棍 （codevs 3498）题解

【问题描述】  

    乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过100。

   现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

   给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

【样例输入】

     9 

    5 2 1 5 2 1 5 2 1

【样例输出】

     6

【解题思路】

     这道题的核心思想就一个字，搜……首先找到最大的那一段，原始木棍的可能长度必定>=最大的那一段木棍的长度，所以我们从最大的那一段长度开始往木棍总长度搜，将木棍排序，定义f布尔型数组，用来存该木棍是否用过，由于最终必定每一根木棍都可以成为组成的一部分，因此我们只要碰到没用过的就搜即可，如果有一根无法组成，那就不是原始木棍的长度，搜下一个长度，详见代码。

【代码实现】

var a:array[0..100] of longint;
    f:array[0..100] of boolean;
    n,i,s,maxn,now,j:longint;
    flag:boolean;
procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
function pd(sum,v:longint):boolean;
var i:longint;
begin
 pd:=false;
 if sum=now then
  exit(true);//如果等于当前所搜的长度，就暂时是正确的，可以搜其他没有搜的木棍
 if sum>now then
  exit(false);//如果大于了，那么就剪枝，搜下一根木棍
 for i:=v downto 1 do
  if f[i] then
   if pd(sum+a[i],i-1) then
    begin
     f[i]:=false;
     exit(true);
    end;
end;
begin
 readln(n);
 for i:=1 to n do
  begin
   read(a[i]);
   s:=s+a[i];
   if a[i]>maxn then
    maxn:=a[i];
  end;
 sort(1,n);
 for i:=maxn to s do//从最长的搜到总长
  if s mod i=0 then
   begin
    now:=i;
    flag:=true;
    fillchar(f,sizeof(f),true);
    for j:=n downto 1 do
     if f[j] then
      if not pd(a[j],j-1) then//凡是没有用过的木棍都要搜一遍，只要有一根不能组成就搜下一个长度
       begin
        flag:=false;
        break;
       end;
    if flag then
     begin
      writeln(i);
      halt;
     end;
   end;
end.