Sticks POJ - 1011 少林神棍 dfs四次剪枝

http://poj.org/problem?id=1011

题意：若干根棍子被截成小段的木棒，现在给你这些木棒，问最短可以拼出的棍子长度。

题解：搜索，dfs（r,m) 二个参数分别代表还剩r个木棒，当前棍子还剩m长度。

从dfs(N,L)搜到dfs(0,0)停止。

棍子从大到小排序

从小到大枚举L

四个剪枝

0.考虑木棒大多都一样长的特殊情况。

多余的枚举：

“如果某个木棒在当前棍子不能用，那么之后必定会用到”

1.第一个木棒回溯时（由于后续无法继续拼接导致不能用），后面总归会还是要把它作为某棍的第一棒（因为它是第一个也就说明是最长的）来处理的。所以直接跳到下一种长度。

2.最后一个木棒回溯时（由于后续无法继续拼接导致不能用），试图将其用短棒子代替并得到一解。那么这个木棒可以通过与短木棒们交换来获得另一个之前判掉的解。产生矛盾。

“顺序枚举"

3.前后木棒长短顺序。如果短的在长的前面，说明长的在前面的情况已经被判掉了，当然，长的在前面的情况里必然已经包括了先长后短的情况。

坑：用rep模板的时候，全局变量写在rep里面会被定义成局部的orz 不但里面用不了，循环后也会丢失最后循环结束的数据。

#define _CRT_SECURE_NO_WARNINGS

#include<cstring>

#include<cctype>

#include<cstdlib>

#include<cmath>

#include<cstdio>

#include<string>

#include<stack>

#include<ctime>

#include<list>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<sstream>

#include<iostream>

#include<functional>

#include<algorithm>

#include<memory.h>

//#define INF 0x3f3f3f3f

#define eps 1e-6

#define pi acos(-1.0)

#define e exp(1.0)

#define rep(i,t,n)  for(int i =(t);i<=(n);++i)

#define per(i,n,t)  for(int i =(n);i>=(t);--i)

#define mp make_pair

#define pb push_back

#define mmm(a,b) memset(a,b,sizeof(a))

//std::ios::sync_with_stdio(false);

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

void smain();

#define ONLINE_JUDGE

int main() {

    ios::sync_with_stdio(false);

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

    long _begin_time = clock();

#endif

    smain();

#ifndef ONLINE_JUDGE

    long _end_time = clock();

    printf("time = %ld ms.", _end_time - _begin_time);

#endif

    return ;

}

const int maxn = 4e5 + ;

const ll mod = 1e7 + ;

const ll INF = ()*(200000ll) + ;

int N, L;

int vis[];

int totallen = ;

int last;

vector<int>anlength;

stack<int >temp;

bool dfs(int r, int m) {

    if (r ==  && m == ) {

        return true;

    }

    if (m == )

    {    m = L; }

    int start = ;

    if (m!= L) start = last + ;

    rep(i, start, N-) {

        if (!vis[i] && anlength[i] <= m) {

            if (i > ) {

                if (vis[i - ] ==  && anlength[i] == anlength[i - ])continue;//consider all length is same

            }

            vis[i] = ; last = i;//consider order

            if (dfs(r - , m - anlength[i])) {return true; }

            else {

                vis[i] = ;

            if (anlength[i] == m||L == m)return false; //某长度下，  某根棍子的第一根木棒不能用，说明这根木棒废了，直接换下一个长度。

            //if (anlength[i] == m)return false;//最后一根木棒不能用，直接换下一个长度。

            }

        }

    }

    return false;

}

string s;

int a, b, c,ans;

void Run() {

    rep(i, anlength[], totallen/) {

        L = i;

        if (totallen%L)continue;

        mmm(vis, );

        if (dfs(N, L)) {

            cout << L << endl;

            return;

        }

    }

     {

        cout << totallen << endl;

    }

}

void smain() {

    while (cin >> N) {

        if (N == )break;

         totallen = ;

        anlength.clear();

        rep(j, , N) {

            int n;

            cin >> n;

            anlength.push_back(n);

            totallen += n;

        }

        sort(anlength.begin(), anlength.end(),greater<int>());

        Run();

    }

}

DFS

Sticks POJ - 1011 少林神棍 dfs四次剪枝