洛谷P1120小木棍[DFS]

题目描述

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

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

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

输入输出格式

输入格式:

输入文件共有二行。

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

(管理员注:要把超过50的长度自觉过滤掉,坑了很多人了!)

第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

输出格式:

输出文件仅一行,表示要求的原始木棍的最小可能长度

输入输出样例

输入样例#1:
9
5 2 1 5 2 1 5 2 1
输出样例#1:
6
-----------------------------------------
[DFS+剪枝]
考虑枚举这个长度,发现答案区间为 [mx,sum]且 len | sum
剪枝:1.从大到小排序,对于一个大木棍 小木棍是从长到短组装的,体现在now上(不用这个now优化也行)
   2.当一个小木棍接入后,当前处理的大木棍刚好达到要求的长度的话,没必要用更多的小木棍代替这个刚接入的小木棍,体现在l+a[i]==len break
   3.当处理完一个大木棍之后,接入下一个大木棍的第一根小木棍用剩下的最长的小木棍,体现在l==0 break

DFS----->当前使用小木棍数,当前组装的长度,当前从大到小到了哪个木棍
//
// main.cpp
// 小木棍
//
// Created by abc on 16/8/13.
// Copyright © 2016年 abc. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n,a[N],tmp,cnt=,mx=-,sum=; bool cmp(int a,int b){
return a>b;
}
int len,ok=,vis[N]; void dfs(int tot,int l,int now){
if(ok) return;
if(tot==cnt && l==) {ok=;return;}
int last=-;
for(int i=now;i<=cnt;i++)
if(vis[i]==&&l+a[i]<=len){ //printf("t %d %d\n",i,l);
if(l+a[i]==last) continue;
last=l+a[i];
vis[i]=;
if(l+a[i]==len) dfs(tot+,,);
else dfs(tot+,l+a[i],i+);
vis[i]=;
if(l== || l+a[i]==len) break;
}
}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&tmp);
if(tmp<=) {a[++cnt]=tmp; mx=max(mx,tmp); sum+=tmp;}
}
sort(a+,a++cnt,cmp); for(len=mx;len<=sum;len++)
if(sum%len==){
ok=;//cout<<len<<"\n";
dfs(,,);
if(ok) break;
}
cout<<len;
return ;
}
 
上一篇:在线LCA模板


下一篇:Android 单字阅读