(luogu1120)小木棍

发表于 | 分类于 ， ，

一个经典剪枝题

思路:

dfs

当然纯的dfs绝对会TLE, 所以要考虑剪枝

  1. 小木棍所能拼成的木棍长度一定是小木棍长度总和的整除数, 且小于小木棍中最长的

  2. 搜索时首先考虑能用的小木棍中最长的, 如果无法拼成则直接返回

  3. 用桶储存小木棍, 这样可以更轻松地做到(2), 且可以避免考虑同样长度的小木棍

  4. 如果考虑某根小木棍时, 已经到达目标长度, 但在后面的搜索中未能找到解, 直接返回. 因为后面的小木棍一定更短, 如果考虑后面的小木棍不会更优

具体方法结合代码理解

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Mn(70);
inline int _max(const int& x,const int& y)
{ return x>y ? x : y; }
inline int _min(const int& x,const int& y)
{ return x<y ? x : y; }
int n;  //小木棍根数
int sum,mx,mn(60);  //小木棍总长, 小木棍最长值, 小木棍最短值(方便枚举)
int st[Mn]; //小木棍(用桶存储(剪枝3))
void dfs(int rs,int nsm,int ns,int tar) //剩余需拼木棍总数, 当前所拼木棍长度, 当前考虑长度, 目标长度
{
    if(!rs) //如果全部拼完
    {
        cout << tar;
        exit(0);    //直接输出结束程序
    }
    if(nsm==tar)    //当前木棍已拼完
    {
        dfs(rs-1,0,mx,tar); //考虑下个木棍
        return;
    }
    for(int i(ns);i>=mn;--i)    //剪枝2
    {
        if(st[i] && nsm+i<=tar)
        {
            --st[i];
            dfs(rs,nsm+i,i,tar);
            ++st[i];
            if(nsm==0 || nsm+i==tar)    break;  //剪枝2与剪枝4
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i(1);i<=n;++i)
    {
        int x; scanf("%d",&x);
        if(x<=50)   //需去除大于50的数据
        {
            ++st[x];
            sum += x;
            mx = _max(mx,x);
            mn = _min(mn,x);
        }
    }
    for(int i(mx);i<=sum;++i)
        if(!(sum%i))    //剪枝1
            dfs(sum/i,0,mx,i);
    return 0;
}