题解 P1120 【小木棍 ［数据加强版］】

· · 题解

终于AC~

第一遍的时候打的暴力 没得多少分

后来发现原来dfs+剪枝是正解

1.题目中说了 >50的自动忽略

2.先排好序 直接从第一个开始搜索

3.dfs(剩下的长度，第几个木棍开始，已经摆好了几组)

4.剪枝一：保证木棍总长度sum能整除你假设的长度

5.怎样就能求出可以摆多少组 然后就有递归终止条件了

6.当前这一根已经摆完 剩下的长度应该重新开始 于是我们必须记录下假设的长度

7.vis数组保证这个数据只能用一次

8.剪枝二：用了当前木棍后无法拼好 但是剩下的木棍长度还等于当前木棍长度 跳出

9.剪枝三：首先：能运行到这表明最大的a[i]也不能满足条件 然后：如果len==pp 即一组新的木棍 那么以后的也不能满足条件

10.剪枝四：当前长度不行 其他长度也不行

（代码中还会有注释 欢迎收看！！！ 望通过）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue> 
#define MAXN 100005
#define LL long long
#define INF 2147483640
#define MOD 100000007
#define free(s) freopen("s.txt","r",stdin);
using namespace std;
bool cmp(int x,int y)
{
    return x>y;
}
int n,t,sum=0,cnt=0,a[70],res,vis[70],pp;
int dfs(int len,int sta,int now)// dfs(剩下的长度，第几个木棍开始，已经摆好了几组) 
{
    if(now==res)
        return 1;
    if(len==0)
        if(dfs(pp,1,now+1))// 当前这一根已经摆完 剩下的长度应该重新开始 
            return 1;
    for(int j=sta;j<=cnt;j++)
        if(!vis[j]&&a[j]<=len)
        {
            vis[j]=1; // 保证点未被用过 
            if(dfs(len-a[j],j+1,now)) // 搜下一个点 
                return 1;
            vis[j]=0;
            if(len==a[j]||len==pp)// 首先：能运行到这表明最大的a[i]也不能满足条件 然后：如果len==pp 即一组新的木棍 那么以后的也不能满足条件 
                break; // 用了当前木棍后无法拼好  但是剩下的木棍长度还等于当前木棍长度 跳出 
            while(a[j+1]==a[j]) // 当前长度不行 其他长度也不行 
                j++;
        }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);
        if(t<=50)
        {
            sum+=t;
            a[++cnt]=t;
        }
    }
    sort(a+1,a+1+cnt,cmp);
    for(int i=a[1];i<=sum;i++)
        if(sum%i==0)
        {
            pp=i; // 全局记录长度 
            res=sum/i;
            if(dfs(i,1,0))
            {
                printf("%d",i);
                return 0;
            }
        }
    return 0;
}