小木棍

暴力搜索

#include <cstdio>
#include <cstdlib>
#include <cstring>


int n=0,m;
int a[110];                         //桶
int p=0;                            //木棍总长度
int max=0,min=51;                   //最长的木棍的长度以及最短的木棍的长度
int ans;                            //记录当前成功拼接了几根木棍，在dfs中用到


void dfs(int x,int y,int z)         //x表示每根木棍的期望长度，y表示现在拼成的长度，z表示上一次使用的木棍的长度
{
  if(ans*x==p)                      //假如拼接成功
  {
    printf("%d",x);
    exit(0);                       //直接结束，此时一定是最优解，因为他要的是最小的解
  //而我们是从小到大枚举的，第一个解必然是最优解
  }
  for(int i=z;i>=min;i--)         //因为较长的木棍更难拼，所以从长的先开始
  {
    if(a[i]&&y+i<=x)              //假如还有长度为i的木棍以及拼接起来不会超过期望长度的话
    {
      y+=i;
      if(y==x)ans++,y=0;
      a[i]--;                    //减去桶内的木棍
      if(y==0)dfs(x,0,max);      //如果拼接成功，则z要从max开始
      else dfs(x,y,i);
      a[i]++;                   //归来返还桶内的木棍
      if(ans>0&&y==0)y=x-i,ans--;     //已经拼好的木棍打乱重新排列
      else y-=i;                      //没拼好的木棍减去归来的折断木棍长度
      if(y==0 || y+i==x)break;
      /*剪枝：剩余长度等于x，如果i不成功，因为i是剩余最长的，所以再往后找短棍，下一次也避不开i，索性就递归会上一次，但是递归回来后，面临期望长度的最后一个木棍，
      需要用两根短棍拼接一根i棍，因为下一次的拼接木棍失败了，剩余的两根或多个短棍换一根长棍，再拼接新的期望长度也不会成功，直接就再递归回去一次*/
    }
  }
}


int main()
{
  scanf("%d",&m);
  memset(a,0,sizeof(a));       //一定要记得初始化！！！
  for(int i=1;i<=m;i++)
  {
    int x;
    scanf("%d",&x);
    if(x<=50)                 //过滤掉超过50的
    {
      a[x]++,p+=x;
      max=max<x?x:max;
      min=min>x?x:min;
    }
  }
  for(int i=max;i<=p/2;i++)   //枚举原本木棍的长度，用dfs尝试是否能拼接成功
  /*由于原本木棍的长度不可能比最长的木棍长度要短，所以从max开始
  以及原本木棍的长度一定能整除总长度（商为1的情况下面会处理），所以假如i>p/2的时候
  i一定不能整除p，所以没必要dfs，直接跳过*/
  {
    if(p%i==0)               //如果不能整除则跳过（不能整除则说明会有余数，也就是多余的木棍）
    {
      ans=0;                 //一定要记得初始化！！！
      dfs(i,0,max);
    }
  }
  printf("%d",p);           //假如上面未成功，就只能把全部拼在一起了
  return 0;
}

笔记：这个题目虽然是爆搜题，但是优化的很好，比如：因为木棍长度受限，就将木棍放到桶里节省空间，而且还顺便排好了顺序，还有，如果期望长度超过总长度就输出总长度，再就是，期望长度筛选能被总长度整除的。最难的就是那个剪枝，链接给的说明很模糊，这道题的剪枝思考好久才想明白这个逻辑。