搜寻题超时，求修改，求剪枝。poj1011

搜索题超时，求修改，求剪枝。。。poj1011

C/C++ code

#include<cstdlib>#include<iostream>#include<cstdio>#include<cmath>#include<set>#include<cstring>#include <algorithm>#define N 66using namespace std;int a[N];bool v[N];int n;int minv;bool dfs(int cur,int k,int s){    if(k==n)return 1;    int chong=-1;    for(int i=s ; i<n; i++)    {        if(chong!=a[i]&&!v[i]&&cur+a[i]<=minv)        {            v[i]=1;            if(cur+a[i]<minv)            {                if(dfs(cur+a[i],k+1,i+1))                    return 1;            }            else            {                if(dfs(0,k+1,0))                    return 1;                return 0;            }            v[i]=0;            if(cur==0)                return 0;            chong=a[i];        }    }    return 0;}bool cmp(int a,int b){    return a>b;}int main(){//    freopen("ex.in","r",stdin);    while(scanf("%d",&n)&&n)    {        memset(v,0,sizeof(v));        int sum=0;        for(int i=0; i<n; ++i)        {            scanf("%d",&a[i]);            sum+=a[i];        }        sort(a,a+n,cmp);        minv=a[0];        int flag=1;        for(int i=n-1; i>=0; i--)        {            if(!(sum%minv))            {                if(dfs(0,0,0))                {                    printf("%d\n",minv);                    flag=0;                    break;                }            }            minv+=a[i];        }        if(flag)            printf("%d\n",sum);    }    return 0;}

C/C++ code

#include<iostream>#include<algorithm>using namespace std;int sticks[64],n,len,num;bool used[64];bool compare(int a,int b){    return a>b;}bool dfs(int cur,int left,int level){    if(left==0)    {        if(level==num-2)            return true;        for(cur=0;used[cur];cur++);        used[cur]=true;        if(dfs(cur+1,len-sticks[cur],level+1))            return true;        used[cur]=false;        return false;    }else    {        if(cur>=n-1)return false;        for(int i=cur;i<n;i++)        {            if(used[i])continue;            if((sticks[i]==sticks[i-1])&&!used[i-1])                continue;            if(sticks[i]>left)continue;            used[i]=true;            if(dfs(i,left-sticks[i],level))               return true;            used[i]=false;        }        return false;    }}int main(){   // freopen("in.txt","r",stdin);    while(cin>>n)    {        if(n==0)break;        int sum=0;        for(int i=0;i<n;i++)        {            scanf("%d",&sticks[i]);            sum+=sticks[i];        }        sort(sticks,sticks+n,compare);        bool end=false;        for(len=sticks[0];len<=sum/2;len++)        {            if(sum%len==0)            {                used[0]=true;                num=sum/len;                if(dfs(0,len-sticks[0],0))                {                    end=true;                    printf("%d\n",len);                    break;                }                used[0]=false;            }        }        if(!end)printf("%d\n",sum);        memset(used,0,sizeof(used));    }    return 0;}
[解决办法]
好复杂！