木棒接合poj 1011探索+剪断再帰実現

木の棒のつなぎ合わせ、POJの1011
タイトル:http://poj.org/problem?id=1011
 
        クラシックな検索+枝切り問題.この問題はもう3回目にしましたが、まだめまいがします.自分の検索に対する感覚を話してください.以前は検索アルゴリズムを書いていたが、いつもスタックを使っていた.例えば,迷路問題は,スタックを押して経路を保存し,スタックを弾いて後退する.「歩いてこない時の道」を保証する標識も設置しなければならない.
 
        大牛たちが書いたcodeを見て、後戻り形式の書き方が簡潔だという醍醐味がありました.この書き方はスタック弾スタックのツールをcomplierに渡したので、コードが特に爽やかに見えます.しかし、バラは香ばしいが、体にとげがある.さわやかで簡潔なのは簡単で書きやすいという意味ではありません.これは,関数のパラメータ,戻り値を繰り返し吟味することである.関数にはいくつかのパラメータが必要で、戻り値があるかどうか、再帰的な終了条件は何ですか.
 
        本題に対して、つなぎ合わせる過程はDFSで、つまり:木の棒を絶えず持って試して、1つをつなぎ合わせて次をつなぎ合わせます.パラメータを知る必要があります:現在の接合で得られた木の棒の長さ、接合に成功した木の棒の数、現在試している木の棒の番号.接合の過程は判断する必要があるので、関数はboolを返す.
 
        スタックで実現すると、ロールバックは絶えず弾スタックである.ここでは、ロールバックはあいまいで、すでに設定されているマークを復元するだけです.また,再帰呼び出し時も抽象的である.binary treeに再帰が書かれているように、再帰呼び出しの結果の一部が既知であると仮定してから、後続のコードを書き続けることができます.
 
この問題のもう一つの鍵は、枝を切る条件に使用できる枝を切ることです.
1.      棒の長さを大きくから小さく並べ替えます.
2.      すべての棒の全長を計算し、全長で割り切れる数だけを検索します.
3.      棒の最大長さから検索
4.      前回試した棒の長さを保存し、接合に失敗した場合は同じ長さで繰り返し試す必要はありません.
5.      試した棒のラベルが0に戻るとfalseに戻ります

Problem: 1011		User: 3109034010
Memory: 264K		Time: 16MS
Language: C++		Result: Accepted


#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

//***********************    *****************************

const int MAX_NUM = 70;


//*********************       *************************




//********************        ************************

int stickNum;
int stickLen[MAX_NUM];


//**********************      **************************

int sumLen;
bool used[MAX_NUM];


//***********************    *****************************

bool FindStick( int curId, int curLen, int curNum, int targetLen )
{
	if( curNum == sumLen / targetLen )
	{
		return true;
	}
	if( curLen == targetLen )
	{
		return  FindStick( 0, 0, curNum+1, targetLen );
	}
	else
	{
        int i;
    	int pre = 0;
    	for( i=curId; i<stickNum; i++ )
    	{
    		if( pre != stickLen[i] && ( curLen + stickLen[i] <= targetLen ) && !used[i] )
    		{
    			pre = stickLen[i];
                used[i] = true;
                //        
                // FindStick == true ， stickLen[i]                              
    			if( FindStick( i+1, curLen + stickLen[i], curNum, targetLen ) )
    			{
                    break;
                }
                
                used[i] = false;
                //       
                //      i == 0 
                if( curId == 0 )
                {
                    return false;
                }            
    		}
    	}
    	if( i >= stickNum )				
    	    return false;    
        else
            return true; 
    }	
}


//************************main  ****************************

int main()
{
	//freopen( "in.txt", "r", stdin );	
	while( cin >> stickNum, stickNum )	
	{	
        sumLen = 0;
        memset( used, false, sizeof(used) );        
		for( int i=0; i<stickNum; i++ )
		{
			cin >> stickLen[i];             			
			sumLen += stickLen[i];
		}
		sort( stickLen, stickLen + stickNum, greater<int>() );		
        
        int x;
        for( x=stickLen[0]; x<sumLen; x++ )
    	{
    		if( sumLen % x == 0 )
    		{    			
    			if( FindStick( 0, 0, 0, x ) )
    			{
    			    break;
    			}
    		}
    	}
		cout << x << endl;		
	}	 
	return 0;
}