POJ 1011 Sticks

POJ 1011 Sticks

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

DFS

题意是让你把这些木棍组合成长度相等的一些木棍。要求长度最短。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[65],n,sum,ans;
bool v[65],ok;
bool cmpa(int a,int b)
{
    return a>b;
}
bool dfs(int num,int need,int total)
{
    int i;
    if(need==0)
    {
        if(total==sum/ans-2)return 1;
        for(i=0;v[i];i++);
        v[i]=1;
        if(dfs(i+1,ans-a[i],total+1))return 1;
        v[i]=0;
        return 0;
    }
    else
    {
        if(num>=n-1)return 0;
        for(i=num;i<n;i++)
        {
            if(a[i]==a[i-1]&&!v[i-1])
            continue;
            if(!v[i]&&a[i]<=need)
            {
                v[i]=1;
                if(dfs(i,need-a[i],total))return 1;
                v[i]=0;
            }
        }
        return 0;
    }
}
int main()
{
    while(scanf("%d",&n),n)
    {
        sum=ans=0;
        for(int i=0;i<n;i++)
        scanf("%d",&a[i]),sum+=a[i];
        sort(a,a+n,cmpa);
        memset(v,0,sizeof(v));
        ok=0;
        for(ans=a[0];ans<=sum/2;ans++)
        {
            if(sum%ans==0)
            {
                v[0]=1;
                if(dfs(0,ans-a[0],0))
                {printf("%d\n",ans);ok=1;break;}
            }
        }
        if(!ok)
        printf("%d\n",sum);
    }
    return 0;
}

还有更强大的剪枝版本号的:

#include<cstdio>
#include<cstring>
#include<cstring>
#define MAX 64
int s[MAX],vis[MAX],n,len,sum;
void input()
{   int i,j,temp;
    sum = 0;
       for(i=0;i<n;i++)
         {
            scanf("%d ",&s[i]);
            sum+=s[i];
         }
      for(i=1;i<n;i++)
       for(j=0;j<n-i;j++)
       {
           if(s[j]<s[j+1])
          {
           temp = s[j];
           s[j] = s[j+1];
           s[j+1] = temp;
          }
       }
}
bool dfs(int now_len,int i,int count)
{
    if((count+1)*len==sum)
    {
        return true;
    }
    for(int k= i;k<n;k++)
    {
       if(vis[k]) continue;
       if(k&&!vis[k-1]&&s[k]==s[k-1]) continue;
       if(s[k]+now_len>len) continue;
       if(now_len+s[k]==len)
       {
           vis[k]=1;
           bool result = dfs(0,0,count+1);
           vis[k]=0; 
           return result;
       }
       else if(now_len==0)
       {
           vis[k]=1;
           bool result = dfs(s[k],k+1,count);
           vis[k]= 0;
           return result;
       }
       else if(now_len+s[k]<len)
       {
           vis[k] = 1;
           bool result = dfs(s[k]+now_len,k+1,count);
           vis[k] = 0;
           if(result)
           return true;
       }
    }
    return false;
}
int main()
{
    while(scanf("%d",&n),n)
    {
       input();
       for(len=s[0];len<=sum;len++)
       {
           if(sum%len) continue;
           memset(vis,0,sizeof(vis));
           if(dfs(0,0,0))
           break;
       }
       printf("%d\n",len);
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118378.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Docker(一):Docker的安装与常用命令

    Docker(一):Docker的安装与常用命令

  • 机器学习之朴素贝叶斯算法详解

    机器学习之朴素贝叶斯算法详解1-1基本流程朴素贝叶斯公式:P(A|B)=P(A)P(B|A)P(B)P(A|B)=P(A)P(B|A)P(B)P(A|B)=\frac{P(A)P(B|A)}{P(B)}一、概率基础知识:条件概率是指事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为:P(A|B),读作“在B条件下A的概率”。若只有两个事件A,B,那么:P(AB)=P…

    2022年10月23日
  • Convert Sorted List to Binary Search Tree「建议收藏」

    Convert Sorted List to Binary Search Tree

  • linux动态库和静态库的使用_静态库的使用

    linux动态库和静态库的使用_静态库的使用文章目录动静态库的基本原理认识动静态库动静态库各自的特征静态库的打包与使用打包使用动态库的打包与使用打包使用动静态库的基本原理动静态库的本质是可执行程序的“半成品”。我们都知道,一堆源文件和头文件最终变成一个可执行程序需要经历以下四个步骤:预处理:完成头文件展开、去注释、宏替换、条件编译等,最终形成xxx.i文件。编译:完成词法分析、语法分析、语义分析、符号汇总等,检查无误后将代码翻译成汇编指令,最终形成xxx.s文件。汇编:将汇编指令转换成二进制指令,最终形成xxx.o文件。链接

  • Alex 的 Hadoop 菜鸟教程: 第2课 hadoop 安装教程 (CentOS6 CDH分支 yum方式)「建议收藏」

    Alex 的 Hadoop 菜鸟教程: 第2课 hadoop 安装教程 (CentOS6 CDH分支 yum方式)「建议收藏」前提条件:系统是centos6安装之前1.安装jdkcdh5对应的jdk是oracle-jdk1.7.0_25,注意是oracle-jdk,千万别yuminstalljdk就完事了,因为那样装的是openjdk到这边http://www.oracle.com/technetwork/java/javase/downloads/java-archiv

  • 微信域名防屏蔽防封系统,轻松微信中域名网站被屏蔽被封的问题「建议收藏」

    微信域名防屏蔽防封系统,轻松微信中域名网站被屏蔽被封的问题「建议收藏」做微信营销活动,域名没被封过,那你的营销人生肯定是不完整的。如果做到微信域名防封呢?这就要借助一些工具来实现有效的防封措施了。 第一步你需要有一个微信域名检测接口,自己开发或是购买都可以。第二步配置你的程序,用三套域名A、B、C,比如说分享出去的域名是A,这里面A被称作是主域名。点开后跳到B,跳转之前检测一下B有没有被封,这里面的B就称作是落地域名。通常情况下落地域名B…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号