poj 1011

附上代码，里面有注释！  0MS！

[cpp] 
#include <stdio.h> 
#include <stdlib.h> 
 
 
int sticks[64]; 
int used[64]; 
int stick_num=0; 
int target_num =0; 
int target_length=0; 
int run_time; 
int compare(const void *a, const void *b) 
{ 
    return *((int*)b)-*((int*)a); 
} 
 
 
int search(int stick_index,int left, int cur_index) 
{ 
    //如果成功配对一根 
    if(left == 0) 
    { 
        if(stick_index == target_num-1) 
            return 1; 
 
 
        stick_index++; 
        for(cur_index=1;used[cur_index]==1;cur_index++) 
          ; 
        left = target_length; 
        used[cur_index]=1; 
        if(search(stick_index,left-sticks[cur_index],cur_index+1) == 1) 
                return 1; 
        used[cur_index]=0; 
        return 0; 
    } 
    else 
    { 
        int i=0; 
        for(i=cur_index;i<stick_num;i++) 
        { 
            if(used[i]==0 && sticks[i]<=left) 
            { 
                if(used[i-1]==0 && sticks[i]== sticks[i-1])  //剪枝1，重要 
                    continue; 
                run_time++ ; 
                used[i] = 1; 
                if(search(stick_index,left-sticks[i],i+1) == 1) 
                    return 1; 
                used[i] = 0; 
                if(sticks[i] == left || left == target_length)  //剪枝2、3，重要 
                { 
                    return 0; 
                } 
            } 
        } 
        return 0; 
    } 
} 
int main() 
{ 
    int n = 0; 
    int sum; 
    while(1) 
    { 
        scanf("%d",&n); 
        if(n==0) 
            break; 
 
 
        sum = 0; 
        int i=0; 
        int max=0; 
        stick_num = n; 
        for(i=0;i<n; ++i) 
        { 
            scanf("%d",&sticks[i]); 
            sum += sticks[i]; 
            if(sticks[i]>max) 
                max = sticks[i]; 
        } 
        memset(used,0,sizeof(used)); 
        qsort(sticks,n,sizeof(int),compare); //优化数组，减少搜索次数 
        for(i=stick_num;i>0;i--) 
        { 
            if(sum%i == 0 &&(sum/i)>=max) 
            { 
                target_num = i; 
                target_length = sum/i; 
                run_time = 0; 
                used[0] = 1; 
                if(search(0,target_length-sticks[0],1)) 
                { 
                    //printf("run %d times, %d\n",run_time,target_length); 
                    printf("%d\n",target_length); 
                    break; 
                } 
            } 
        } 
    } 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：C++ vector MSDN简单入门解释
下一个：定点小数补码一位乘（Booth比较法）