洛谷 P1120 小木棍 dfs+剪枝

Problem Description

[题目链接] https://www.luogu.com.cn/problem/P1120

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

Input

共二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65

Output

一个数，表示要求的原始木棍的最小可能长度

Sample Input

9

5 2 1 5 2 1 5 2 1

Sample Output

Analysis of ideas

枚举每个可能的长度,从最长的开始,到木棍长度之和(一根)

剪枝非常非常关键

我觉得最重要的剪枝,也是卡了我最久的剪枝if(len == 0 || aim-len == a[i]) return false;

主要分析一下这句话,当这句话执行的时候说明什么?说明回溯了,而如果回溯了的话说明什么,说明前面dfs没有返回true,当len回溯回0的时候,说明一开始选的这根木棍,拼不成aim长度,那么就没必要搜了,另一个就是当len+a[i] == aim都没有返回true,那也没必要搜了

其他的剪枝看代码吧

Accepted code

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

using namespace std;

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

#define cin(a) scanf("%d",&a)

#define pii pair<int,int>

#define ll long long

#define gcd __gcd

const int inf = 0x3f3f3f3f;

const int maxn = 100;

int n,m,t,sum,aim; //t是有效木棍根数,sum是木棍总长度,aim是目标长度

int a[maxn];                //木棍长度

bool vis[maxn];

bool dfs(int cnt,int len, int pos)  //还要拼的根数,拼了的长度,以及下标

{

    if(cnt == 1) return true;          //拼成功了

    if(len == aim) return dfs(cnt-1,0,0);

    for(int i = pos; i < t; i++)          //a从小到大排序

    {

        if(!vis[i] && len+a[i] <= aim)      //选取长度不超过aim的

        {

            vis[i] = 1;

            if(dfs(cnt,len+a[i],i+1)) return true;

            vis[i] = 0;                     //回溯

            if(len == 0 || aim-len == a[i]) return false;   //拼失败了

            while(i+1 < n && a[i+1] == a[i]) i++;       //长度一样的没必要重复搜索

        }

    }

    return false;

}

int main()

{

#ifdef ONLINE_JUDGE

#else

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

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

#endif

    scanf("%d",&n);

    for(int i = 0; i < n; i++)

    {

        scanf("%d",&m);

        if(m <= 50)

        {

            a[t++] = m;

            sum += m;

        }

    }

    sort(a,a+t,greater<int>());         //从大到小排序

    int ans = 0;

    for(int i = a[0]; i <= sum; i++)    //i是枚举长度

    {

        if(sum%i == 0)        //dfs能被sum整除的i

        {

            for(int i = 0; i < t; i++) vis[i] = 0;

            aim = i;                //要拼的长度

            if(dfs(sum/i,0,0))

            {

                ans = i;

                break;

            }

        }

    }

    printf("%d\n",ans);

    return 0;

}

巴特西