Chinaunix首页 | 论坛 | 博客
  • 博客访问: 473476
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-02 16:39:08

题目描述:
若干木棒被截成最多64段,要把它们都组合起来,找到原棒的最短长度,如被截成1,2,3。则最短棒长为3,若被截成1,6,15,则最短棒长为22。
思路:
每段长非递减排序后,由大开始选,依次加到与枚举的原棒长相等,并标记每个已用于组合的小段。直到所有都使用,并且能组合为枚举的最小原长。否则原棒长要枚举到总榜长为止。

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. #ifndef ONLINE_JUDGE
  5. #include<time.h>
  6. #endif

  7. #define YES 1
  8. #define NO 0



  9. int stick[70][2];//二维数组分别存每截棒长和(排序后)下一个不同于它的长度的位置(行标)
  10. int used[70];//记录每截棒是否已被用于组合原棒
  11. int min_stick_len;//最短原棒长
  12. int m;//所有原棒被截得的总段数
  13. int stick_num;//原棒的数量

  14. int compare(const int *a, const int *b)
  15. {
  16.     return *(int*)b - *(int *)a;
  17. }

  18. void Init_Next()
  19. {
  20.     int i, j, t;
  21.     for (i=0; i<m; i=j)
  22.     {
  23.         t = i;
  24.         j = i+1;
  25.         while (stick[j][0] == stick[t][0])
  26.         {
  27.             j++;
  28.         }
  29.         while (t<j)
  30.         {
  31.             stick[t++][1] = j;
  32.         }
  33.     }
  34. }

  35. //查找组合可能,形参为当前可组合木棍的位置,当前组合的长度,当前已组合的木棍数量
  36. int dfs(int cur, int cur_len, int num)
  37. {
  38.     int i, start;
  39.     start = (cur_len==0 ? YES : NO);
  40.     if (num == stick_num)
  41.     {
  42.         return YES;
  43.     }
  44.     for (i=cur; i<m; i++)//从头到尾枚举
  45.     {
  46.         if (used[i])
  47.         {
  48.             continue;
  49.         }
  50.         if (cur_len + stick[i][0] < min_stick_len)//组合长度不足最短原木棒长度
  51.         {
  52.             used[i] = YES;
  53.             if (dfs(i, cur_len + stick[i][0], num))//继续加长度组合
  54.             {
  55.                 return YES;
  56.             }
  57.             used[i] = NO;
  58.             if (start)//如果组合每根原木棒选的第一个长度不符合就跳出选下一个
  59.             {
  60.                 return NO;
  61.             }
  62.             i = stick[i][1]-1;//如果同种长度的一种不满足, 则直接查找下一个不同长度的木棒
  63.         }
  64.         else if (cur_len + stick[i][0] == min_stick_len)//组合长度等于最短原木棒长度
  65.         {
  66.             used[i] = YES;
  67.             if (dfs(-1, 0, num+1))//长木棒数加一, 再次搜索
  68.             {
  69.                 return YES;
  70.             }
  71.             used[i] = NO;
  72.             return NO;
  73.         }
  74.     }//end of for
  75.     return NO;
  76. }

  77. int main()
  78. {
  79.     int i, j, n;
  80.     int sum;//木棒总长
  81.      int cur = 0, cur_len = 0, num = 0;
  82.      #ifndef ONLINE_JUDGE
  83.     freopen("in.txt", "r", stdin);
  84.     #endif
  85.     while (scanf("%d", &m), m)
  86.     {
  87.         memset(stick, 0, sizeof(stick));
  88.         sum = 0;
  89.         for (i=0; i<m; i++)
  90.         {
  91.             scanf("%d", &stick[i][0]);
  92.             sum += stick[i][0];
  93.         }
  94.         qsort(stick, m, sizeof(stick[i]), compare);//每截棒长非递减排序
  95.         //查找排序后的每截木棍后第一个长度不同的木棍的位置
  96.         Init_Next();
  97.         for (min_stick_len=stick[0][0]; min_stick_len<=sum; min_stick_len++)
  98.         {
  99.             memset(used, 0, sizeof(used));
  100.             if (sum % min_stick_len != 0)//最短原棒长必然是总长的度的因子
  101.             {
  102.                 continue ;
  103.             }
  104.             stick_num = sum / min_stick_len;
  105.             if (dfs(cur, cur_len, num+1))
  106.             {
  107.                 printf("%dn", min_stick_len);
  108.                 break;
  109.             }
  110.         }
  111.     }
  112.        #ifndef ONLINE_JUDGE
  113.     printf("used time = %.3lfn",(double)clock()/CLOCKS_PER_SEC);
  114.     #endif
  115.     return 0;
  116. }
  117. //end of program.

  118. //要搜索各种情况, 必须排序后再组合
  119. //因为当判断某一长度不满足组合情况后,就没必要再次判断与它长度相同的其它棒,可直接跳到下一个长度不同的棒.
  120. //所以加70行的i = stick[i][1]-1;会比while(stick[i][0] == stick[i+1][0]) i++;快0.12s左右.
2010-10-02 13:39 发表于百度空间,今搬至CU。
阅读(1201) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~