題目：Sticks

題意：起初有一些相等的木棍，然后被人砍成了n個木條。長度分別給出，現在需將n個木條組合拼成回原來的木棍，問原始木棍的最小可能長度？

思路：雖然知道用dfs，但沒想到怎么實現多個相等的判斷，然后參考了后做的，其實還是那些套路，就是變通不了。。。不過這個剪枝比較NB。。。

（1）枚舉：枚舉原始木棍長度，從總長度/i   i時n~1

（2）搜索：枚舉給出的數組，枚舉位置不是每次都從0開始，而成在遞歸中的pos參數，每次是從上一個的下一位開始的，遞歸中累加上木棍長度，當長度符合枚舉的原始木棍長度時，再繼續搜索，但是參數需要改變，pos從0開始，sum木棍長度也從0開始，當個數繼續+1，當個數與n相等時所有所有木條都組合拼成木棍了。

（3）剪枝：

①遞減排序，可以遞歸層數；

②枚舉原木棍長度應是總長度的倍數且大于最達的木條長度，其他的沒有必要搜索，因為根本達不到！

③當搜索時第i個木條時，第i個木條還未選（即放在還原標記數組的后面）時，如果后面的長度和i的相等，就沒有必要再枚舉，直接i++；（有點懵）

④當第i個木條沒有找到時，沒有必要再繼續尋找了，直接return剪枝。（還是有點懵！）

注意：以后判斷標記數組時用if(visit[i]) continue;  不能和有條件的判斷中加 !visit[i] 這樣時間會很慢！

參考：JeraKrs博客

代碼：

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 100 + 5;bool cmp(int a,int b){return a > b;}int n,stick[maxn],visit[maxn];int ans,len;bool dfs(int steps,int pos,int sum){    if(steps == n) return true;//當到達第n個，說明所以木條都組合拼成了    for(int i = pos;i < n;i++){        if(visit[i]) continue;//關鍵，訪問過的跳過        if(sum + stick[i] < ans){            visit[i] = 1;            if(dfs(steps+1,i+1,sum + stick[i])) return true;            visit[i] = 0;            while(stick[i] == stick[i+1] && i+1 < n) i++;//剪枝：當i個數和第i+i數相等時，不需要再枚舉，因為依然小于ans        }        else if(sum + stick[i] == ans){            visit[i] = 1;            if(dfs(steps+1,0,0)) return true;//當達到組合值時，將組合木條長度和下標位置歸為0，繼續搜索，因為是幾個相等的木條，所以不是找到一個就行。。。            visit[i] = 0;            return false;        }        if(sum == 0) return false;//剪枝：當上面都沒有return時，程序會走到這一步，說明第i個木條沒有找到合適的組合，直接return     }        return false;}inline int solve(){    for(int i=n;i>=0;i--){//從大到小分        if(len % i == 0 && len / i >= stick[0]){//總長度的倍數且平分長度大于初始的最長木條才可進行組合            memset(visit,0,sizeof(visit));            ans = len / i;//當前組合長度            if(dfs(0,0,0)) return ans;        }    }    return -1;}int main(){    while(scanf("%d",&n)!=EOF && n){        len = 0;        for(int i=0;i<n;i++){            scanf("%d",&stick[i]);            len += stick[i];        }        sort(stick,stick+n,cmp);//遞減排序        PRintf("%d/n",solve());    }    return 0;}