洛谷P1120 小木棍 [数据加强版]（搜索）

洛谷P1120 小木棍 [数据加强版]

搜索+剪枝

【剪枝操作】：若某组拼接不成立，且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案时，则可直接跳出循环。因为此时继续枚举其它更小的值时，显然可能情况更少，且同样凑不完。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;

const int maxn = 55;
int cnt[maxn];
int n, tot, max_x, min_x, x;

void dfs(int num, int sum, int target, int p)
{
    if(num == 0){
        printf("%d
", target);
        exit(0);
    }
    if(sum == target){
        dfs(num - 1, 0, target, max_x);
    }
    else{
        for(int i = p; i >= min_x; i--){
            if(cnt[i] && i + sum <= target){
                cnt[i]--;
                dfs(num, sum + i, target, i);
                cnt[i]++;
                if(sum == 0 || sum + i == target){ /***剪枝***/
                    break;
                }
            }
        }
    }
}
int main()
{
    scanf("%d", &n);
    min_x = maxn;
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        if(x <= 50){
            cnt[x]++;
            tot += x;
            min_x = min(min_x, x);
            max_x = max(max_x, x);
        }
    }
    for(int i = max_x; i <= tot; i++){
        if(tot % i == 0){
            dfs(tot / i, 0, i, max_x);
        }
    }
    return 0;
}