poj1011搜索

超时了很多回！看看网上的解题报告，改了改自己的代码，也算是ac了；深度搜索+剪枝，关键还是在于剪枝，在于能想到多少剪枝条件；这样的题好像没什么固定模式，根据某一条件可以判断一些情况！

#include <iostream>
#include <algorithm>
using namespace std;    
int a[65];
int total;
int visited[65];
//int flag;
int dfs(int n,int target,int sum,int flag)
{
    int i,j;
    if(sum==target)
    {
        flag++;
        if(flag==total/target)
            return true;
        sum=0;

    }
    
    for(i=n-1;i>=0;i--)//如果for(i=0;i<n;i++)话一样的超时，不解！
    {
        if(sum+a[i]>target)
            continue;
        if((i!=n-1)&&(a[i]==a[i+1])&&!visited[i+1])
                      continue;
        if(visited[i])
            continue;          
                                       
            sum+=a[i];
            visited[i]=1;
            if(dfs(n,target,sum,flag))
                return true; 
            sum-=a[i];
            visited[i]=0;
            if(sum==0||sum+a[i]==target)
                return false;
            //break;
        
           
    }
    

   return false;
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        total=0;
        int i,j;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            total+=a[i];
        }
        sort(a,a+n);
        //visited[n-1]=1;
        for(i=a[n-1];i<=total;i++)
        {
            if(total%i!=0)continue;
            memset(visited,0,sizeof(visited));
            if(dfs(n,i,0,0))
               break;
        }
        cout<<i<<endl;
        
    }
    return 0;
}