poj 1011--Sticks(搜索)
2018-06-17 21:56:01来源:未知 阅读 ()
题目链接
Description
Input
Output
Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0
Sample Output
6 5
题意:有n段木棍,要求将这n根木棍拼成x跟长度相同的木棍,要使新的木棍尽量短,输出最小值?
思路:搜索,新的木棍的长度一定大于等于原来木棍的最大值maxlen,小于等于这些木棍的总长度sum,所以从小到大(maxlen~sum)遍历这些值,如果sum%i!=0 ,则肯定不能拼成合法的木棍直接跳过;
如果sum%i==0,那么有可能满足,则进行搜索。搜索过程:一根一根的深搜,记录当前已经拼成几根木棍,当前拼的这跟木棍还差多长,用过的木棍用v[i]进行标记。
代码如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; int start,sum; int v[70]; int check(int num,int rest,int pos) { if(num==sum/start) return 1; rest-=pos; v[pos]--; if(rest==0) { int i; for(i=50; i>=1; i--) if(v[i]) break; int flag=check(num+1,start,i); v[pos]++; return flag; } for(int i=rest; i>=1; i--) { if(!v[i]) continue; int flag=check(num,rest,i); if(flag) return 1; } v[pos]++; return 0; } int main() { int n; while(scanf("%d",&n)&&n) { int maxn=-1; sum=0; memset(v,0,sizeof(v)); for(int i=1; i<=n; i++) { int x; scanf("%d",&x); sum+=x; v[x]++; maxn=max(maxn,x); } for(start=maxn; start<=sum; start++) { if(sum%start!=0) continue; if(check(0,start,maxn)) { printf("%d\n",start); break; } } } return 0; } /** 9 21 16 33 36 19 1 35 6 47 ans=107 43 46 16 47 31 22 48 10 47 25 48 33 31 35 33 14 21 8 22 20 37 20 48 8 18 3 44 28 16 9 50 44 18 46 28 43 49 18 19 31 46 3 43 43 ans=141 */ /** 20 4 2 1 6 6 5 6 9 1 0 6 9 0 4 8 3 2 1 1 6 20 6 8 9 4 5 10 6 5 8 5 5 7 9 6 3 10 3 1 9 9 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:递增序列
- 二叉搜索树_BST 2020-05-30
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- 二叉搜索树3 2020-02-06
- 数据结构---二叉搜索树 2020-02-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash