程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1011

poj 1011

編輯:C++入門知識

附上代碼,裡面有注釋!  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; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved