可是却忘记了协调先导时有多少根木棍和它们的尺寸,给出每段小木棍的尺寸

P1120 小木棍 [数据抓实版]

题材叙述

吉优rge有局地同等长的小木棍,他把那些木棍随意砍成几段,直到每段的长都不当先50。

今日,他想把小木棍拼接成原本的规范,不过却忘记了祥和初叶时有多少根木棍和它们的长短。

交付每段小木棍的长短,编制程序帮她找出原来木棍的纤维恐怕长度。

难题叙述

吉优rge有一对如出一辙长的小木棍,他把那一个木棍随意砍成几段,直到每段的长都不超过50。

如今,他想把小木棍拼接成原来的规范,然则却忘记了投机开班时有多少根木棍和它们的长度。

提交每段小木棍的长度,编制程序帮他找出原本木棍的非常的小恐怕长度。

输入输出格式

输入格式:

 

输入文件共有二行。

先是表现3个独立的平头N表示砍过以后的小木棍的总额,个中N≤陆伍

(管理员注:要把当先50的长短自觉过滤掉,坑了诸几人了!)

其次表现N个用空个隔离的正整数,表示N根小木棍的长度。

永利网上娱乐, 

输出格式:

 

输出文件仅一行,表示供给的本来面目木棍的细小可能长度

 

输入输出格式

输入格式:

 

输入文件共有二行。

首先行为二个独门的平头N表示砍过之后的小木棍的总和,当中N≤6伍

(管理员注:要把超越50的长短自觉过滤掉,坑了累累人了!)

第三行为N个用空个隔离的正整数,表示N根小木棍的尺寸。

 

出口格式:

 

出口文件仅1行,表示需要的本来面目木棍的细微恐怕长度

 

输入输出样例

输入样例#1: 复制

9
5 2 1 5 2 1 5 2 1

出口样例#1: 复制

6

输入输出样例

输入样例#1:

9
5 2 1 5 2 1 5 2 1

出口样例#1:

6

说明

2017/08/05

数量时间限制修改:

-#17 #20 #22 #27四组数据时间限制500ms

-#21 #24 #28 #29
#30伍组数据时间限制一千ms

其它时间限制改为200ms(请放心食用)

难题链接:https://www.luogu.org/problemnew/show/P1120

解题报告:

一道很棒的搜索题,要加一群剪枝才能过,升高一下强力的架势水平.

 

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
int a[66],used[66];
int n,cnt,x,sum,maxx;
#define FOR(s,t) for(register int i=s;i<=t;++i)
inline void dfs(int tot,int t,int sec,int now){
    if(t*sec==sum)printf("%d\n",sec),exit(0);
    if(sum-tot<a[cnt])return;
    if(tot==sec){
        dfs(0,t+1,sec,1);
        return;
    }
    FOR(now,cnt){
        if(!used[i]&&a[i]+tot<=sec){
            used[i]=1;
            dfs(tot+a[i],t,sec,i+1);
            used[i]=0;
            if(a[i]+tot==sec||tot==0)break;
            while(a[i]==a[i+1])++i;
        }
    }
    return;
}
inline bool cmp(int a,int b){
    return a>b;
}
int main(){
    scanf("%d",&n);
    FOR(1,n){
        scanf("%d",&x);
        if(x<=50)a[++cnt]=x,sum+=x,maxx=max(maxx,x);
    }
    sort(a+1,a+cnt+1,cmp);
    FOR(maxx,sum/2)if(sum%i==0)dfs(0,0,i,1);
    printf("%d\n",sum);
    return 0;
}

 

  

 

说明

2017/08/05

数量时限修改:

-#17 #20 #22 #二七 肆组数据时间限制500ms

-#21 #24 #28 #29 #305组数据时限一千ms

任曾几何时间限制改为200ms(请放心食用)

永利网上娱乐 1永利网上娱乐 2

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 70
using namespace std;
int n,a[maxn],sum,b[3251],cnt,nn;
bool vis[maxn],flag;
void dfs(int now,int num,int limit,int s){//当前和,已经选了多少个木棍,枚举到的答案 
    if(flag)return;
    if(now==0&&(sum-s)%limit)return;
    if(now==0&&num==nn){flag=1;return;}
    for(int i=1;i<=nn;i++){
        if(!vis[i]&&a[i]+now<=limit){
            vis[i]=1;
            if(a[i]+now==limit)dfs(0,num+1,limit,s+a[i]);
            else dfs(now+a[i],num+1,limit,s+a[i]);
            vis[i]=0;
        }
    }
}
int main(){
    freopen("Cola.txt","r",stdin);
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(x>50)continue;
        a[++nn]=x;
        sum+=a[nn];
    }
    for(int i=1;i*i<=sum;i++)
        if(sum%i==0){
            b[++cnt]=i;
            if(i*i==sum)break;
            b[++cnt]=sum/i;
        }
    sort(b+1,b+cnt+1);
    for(int i=1;i<=cnt;i++){
        memset(vis,0,sizeof(vis));
        dfs(0,0,b[i],0);
        if(flag){
            printf("%d",b[i]);
            return 0;
        }
    }
}

2九分 裸的查找

永利网上娱乐 3永利网上娱乐 4

/*
显然,dfs搜索的是木棍总长的因数。 

   1. 我们搜索的木棍长度假设是合法的,那么每一组达到了当前长度的木棍组合,一定是存在的。
例如样例:5 2 1 5 2 1 5 2 1 比如说我搜索木棍总长的因数6,我们目前搜的木棍组是(5,1),如果这个6的木棍长度是合法的话,那么必有一组木棍组合是(5,1).
所以当我们搜索的木棍组是(5,1)但在之后的搜索中搜不出长度为6的木棍组,那么这个木棍长度就是非法的。
推广到所有长度,即只要如果当前木棍组达到了木棍长度,却在之后的搜索中的木棍组并不能达到这个木棍长度,那么这个木棍长度就是不合法的。 

   2. sort排序从大到小改变搜索顺序,可以更快(因为我们一旦找到合法数据就可以退出)。 

   3. 我们要从上次搜索的终点往后搜索,所有的原理都离不开第一点。

   4.如果当前这个木棍组的长度+当前的a[i] (a[i]为我们一开始输入的每根被砍碎的木棍的长度),还不能达到当前我们搜索的木棍长度
     那么值相同的a[i]都不能使这个木棍组的长达到木棍组长度,我们的sort排序也为这点提供了基础。
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 70
using namespace std;
int n,a[maxn],cnt,mx,s;
bool cmp(int x,int y){return x>y;}
bool vis[maxn];
void dfs(int ans,int sum,int goal,int now){
    if(sum*goal==s){printf("%d",goal);exit(0);}
    if(s-ans<a[cnt])return;
    if(ans==goal){dfs(0,sum+1,goal,1);return;}
    for(int i=now;i<=cnt;i++){
        if(!vis[i]&&a[i]+ans<=goal){
            vis[i]=1;
            dfs(ans+a[i],sum,goal,i+1);
            vis[i]=0;
            if(ans+a[i]==goal||ans==0)break;
            while(a[i]==a[i+1])i++;
        }
    }
}
int main(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(x>50)continue;
        a[++cnt]=x;s+=a[cnt];mx=max(mx,a[cnt]);
    }
    sort(a+1,a+cnt+1,cmp);
    for(int i=mx;i<=s/2;i++)
        if(s%i==0)dfs(0,0,i,1);
    printf("%d",s);
    return 0;
}

98分 各样剪枝

 

相关文章