The start—— POJ 1011 Sticks

这道题很恶心，变态的dfs就不说了，而且还要剪枝。。。。开始我只想了两种剪枝，果断超时了....╮(╯▽╰)╭ 很不爽....因为对于我这种初学者把这个另类的dfs函数写出来就已经很不容易了。。。。不过这题我最终还是被我AC了哈哈~~鸟神同学来看下我的代码哈~~O(∩_∩)O！

Sticks

Time Limit:1000MS		Memory Limit:10000K
Total Submissions:86241		Accepted:19200

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

这题最后想到了6种剪枝，全用上了。。。
#include<iostream>
#include<deque>
#include<vector>
#include<algorithm>
using namespace std;
struct POS
{
    int vx;
    int start;        
}pow;
int n,calu,ring,sum,mmax,temp;
vector<int>v;
deque<POS> vip;
int vis[65];
int mix[65];
bool next(int id)
{
    if(v[id]==v[id+1])
    {
        if(vis[id+1]==0)
        {
            return true;    
        }
        else
        {
            return false;    
        }
    }
    return false;
}
bool dfs(int ipry,int ix,int rest)
{
    if(rest==0) 
    {
        pow.vx=v[ipry];
        while(vis[ipry]==1 && ipry>=0)
        {
            ipry--;
        }
        if(ipry<0)
        {
            return true;
        }
        else
        {
            vis[ipry]=1;
            vip.push_front(pow);
            if(dfs(ipry,ipry-1,ring-v[ipry]))
            {
                return true;
            }
            vis[ipry]=0;
            vip.pop_front();
            return false;
        }      
    }      
    else    
    {      
        for(int i=ix;i>=0;i--)
        {                       
            if(vis[i]==1)                 //这货不是剪枝啊！我去。。。是谁在说这货是剪枝啊？？剪枝是什么？那就是可有可无的，没有的话只是时间长一点，但是你敢说可以没这个吗？
            {
                continue;
            }                                                    
            if(!vip.empty() && v[ipry]==vip[0].vx)     //剪枝2，非重要，如果这根棒棒上一根棒棒相等，则从它之后的下一个位置开始计算，该剪枝直接为0ms的目标提供了可能。
            {       
                if(i>=vip[0].start) 
                {           
                    i=vip[0].start;
                    continue;
                }   
            }         
            if(next(i))              //剪枝3，很重要！对长度排序后，如果前面一根棒子的长度和他一样，且前面那根没用到，同理！这根也不会用到！该剪枝能对付很恶心的测试数据。
            {
                continue;
            }     
            if(v[i]>rest)             //重要剪枝4，如果棒棒的长度比剩余的要大，直接排除！没有这个剪枝就等着超时吧~
            {
                continue;
            }                        
            if(rest>mix[i])         //辅助剪枝5，该剪枝是剪枝6的辅助剪枝，其实思想还是剪枝6的思想。
            {
                return false;
            }       
            temp=0;                       
            for(int j=i;j>=0;j--)
            {
                if(vis[j]==1)
                {
                    temp+=v[j];
                }
            }
            temp=mix[i]-temp;
            if(rest>temp)       //重要剪枝6，这个剪枝有什么用呢？？呵呵，它的唯一用处就是让你的代码时间变成0ms~~如果除了标记过的剩下的棒子的总和要大于rest，否则RF！
            {
                return false;
            }                               
            if(rest==ring-v[ipry])
            {
                pow.start=i; 
            }
            vis[i]=1;
            if(dfs(ipry,i-1,rest-v[i]))
            {
                return true;
            }
            vis[i]=0;
        }
        return false;
    }  
}
int find(int l,int r)
{
    for(ring=l;ring<=r;ring++）
    {  
        if(sum%ring!=0)                                 //重要剪枝1，如果不能整除的话直接跳过。
        {
            continue;
        }
        memset(vis,0,sizeof(vis));
        vis[n-1]=1;
        vip.clear();
        if(dfs(n-1,n-2,ring-v[n-1]))
        {
            return ring;
        }        
    }
}
int main()
{
    while(cin>>n)
    {
        memset(mix,0,sizeof(mix));
        if(n==0)
        {
            break;
        }
        v.clear();
        sum=0;
        mmax=0;
        for(int i=1;i<=n;i++)
        {
            cin>>calu;
            if(calu>mmax)
            {
                mmax=calu;
            }
            sum+=calu;
            v.push_back(calu);    
        }
        sort(v.begin(),v.end());
        for(int i=0;i<=v.size();i++)
        {
            for(int j=i;j>=0;j--)
            {
                mix[i]+=v[j];
            }   
        }
        find(mmax,sum);
        cout<<ring<<endl;
    }    
    return 0;
}
Memory: 224K     Time: 0MS