2016 UESTC Training for Search Algorithm & String E – 吴队长征婚 dfs剪枝、好题

看了原题的一些结题报告

1. 搜索顺序。首先依据小棒长度进行由大到小的排序，在每一层搜索时首先将长度大的小棒填入

当前原棒中。因为当相对长的小棒占据了原棒的大部分空间后能大大减小可行的搜索状态。

2. 利用排序剪枝。在组合同一支原棒的时候，由于检验小棒是否可用的顺序也是由大到小的，

因此在检验到一支小棒可用时，如果当前棒还合填满，可能填入当前棒的小棒的长度也不会比现在填入

的这支小棒长。因此，增加一个递归参数NEXT表示可能用于组合当前棒的第一支小棒的数组下标。

参数传递时，若当前正好拼成一支原棒，NEXT还原回1，否则将NEXT+1传递给下一层递归。

3. 首次只尝试最长的小棒。在第一次组合拼接某一根原棒时，首先放入的是当前最长的小棒，并且，

如果当前状态可以完成组合，则该小棒必定要放入之后的某一根原棒中，即假设它放在当前原棒中，

若放入后搜索失败，则当前状态必定不可能成功，需要回溯。因此，在RES=0时，若第一次搜索失败，

则不断续当前状态的其它搜索。

至于排序相关的， 本来想用过结构体，然后用谓词cmp，直接用sort排序，其它地方也想相应地

用结构体的数组代替之，感觉复杂度应该是适当降低或者说至少没有增加吧，但TLE。

也许是结构体数组访问成员这样的形式 比 二维数组第二维用 0 1 表示 要慢？

#include 
#include 
#include 
using namespace std;
int n, len, parts, _max, sum, tail;

int l[66][2];
bool used[66];

inline void gettail()
{
    int sum = 0, i;
    for(i = n-1; i >= 0; i--){
        sum += l[i][0];
        if(sum > len) break;
    }
    tail = i;
}


inline int getsumres(int m) {
    int sumres = 0;
    for(int i = m; i < n; i++){
        if (used[i] == false)
        sumres += l[i][0];
    }
    return sumres;
}


bool _search(int res,int nxt,int cpl)
{
    if(res == len){res = 0; nxt = 1; cpl++;}
    if(cpl == parts) return true;
    int i = nxt;
    while(i < n){
        if(used[i] == false){
            if(res + l[i][0] <= len){ used[i] = true; if(_search(res + l[i][0], i+1, cpl)) return true; used[i] = false; if(res == 0) break; //第一次拼接当前原棒无解则当前状态必定无解，跳出 if(res + l[i][0]== len) break; //若尝试一根小棒恰能组合出当前原棒的剩余长度的小棒失败，则不再尝试比它更小的小棒 } i = l[i][1]; if (i >= tail && getsumres(i) < len - res) break;  //计算当前所剩可用小棒是否足以拼出当前这支木棒原型
            continue;
        }
        i++;
    }
    return false;
}

int main() {

    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    while(scanf("%d",&n)){
        if(n == 0) break;
        sum=0;
        for(int i = 0; i < n; i++){
            scanf("%d", &l[i][0]);
            sum += l[i][0];
        }
        //sort()
        int t = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(l[i][0] < l[j][0]){
                    t = l[i][0];
                    l[i][0] = l[j][0];
                    l[j][0] = t;
                }
            }
        }
        int i = 0, j = 0;
        while(i < n){
            j = i + 1;
            while( j < n && l[j][0] == l[i][0]) j++;
            for(int k = i; k < j; k++) l[k][1]=j;
            i = j;
        }


        _max=l[0][0];
        for(len = _max;  len<= sum; len++){ //枚举原棒长度，并判断其能否整除总长度
            if(sum % len == 0){
                parts = sum/len;
                gettail();
                memset(used, false, sizeof used);
                if(_search(0, 0, 0)){
                    printf("%dn",len);
                    break;
                }
            }
        }
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx