首页 > 代码库 > HDU 1455 Sticks

HDU 1455 Sticks

2024-07-16 03:02:26   218人阅读

这题让我看解题报告都感觉弱无力的样子，囧rz

题意：

几根原本长度相同的木棒，然后被某人当出气筒剪啊剪啊，剪成好几段，然后，好吧，这时间一长记性就差了，忘了原来这堆木棒的长度。

输出可能的最短长度

如果说思路大概懂，但是代码看不懂，最好的办法就是在纸上模拟，或者把别人代码在计算机上一步一步跟踪调试。

首先原长可能的范围：

最短也比剪断后的最长木棒长(或者相等)，最长可能就是由一根木棒剪出来的

另外，原木棒长度必然是木棒总长的因数

 

再解释一下代码中DFS各个参数的含义

bool DFS(int len, int l, int count, int pos)
  • len：假设原木棒长度为len，进行搜索。搜索过程中len是不变的
  • l：一个长为len的木棒，可能是由多个剪断后的木棒拼接而成。l表示当前正在还原的木棒的长度，也就是说还需要一个或多个总长为len-l的木棒就能还原成一个长为len的木棒
  • count:如果总长sum，原长为len，则原来一共有sum/len根木棒，count则记录着已经拼好了多少根长为len的木棒
  • pos:此次要拼的木棒的位置

 

 1 #define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 struct Stick 9 {10     int lenth;11     bool used;    //    该木棒是否已经用于拼接12 }sticks[55];13 14 int n, num, sum;15 16 bool cmp(Stick a, Stick b)17 {18     return (a.lenth > b.lenth);19 }20 21 bool DFS(int len, int l, int count, int pos)22 {23     if(len == sum)24         return true;25     if(count == num)26         return true;    //num根木棒已经全部拼接完成27     for(int i = pos; i < n; ++i)28     {29         if(sticks[i].used)30             continue;31         if(len == sticks[i].lenth + l)32         {33             sticks[i].used = true;34             if(DFS(len, 0, count + 1, 0))    //拼好一根，拼下一根35                 return true;36             sticks[i].used = false;37             return false;38         }39         else if(len > sticks[i].lenth + l)40         {41             sticks[i].used = true;        //一根拼不完，先拼上42             l += sticks[i].lenth;43             if(DFS(len, l, count, i + 1))44                 return true;45             sticks[i].used = false;46             l -= sticks[i].lenth;47             if(l == 0)48                 return false;        //这一句不是特别理解 =_=!!49             while(sticks[i].lenth == sticks[i + 1].lenth)50                 ++i;    //如果两根长度相等，这根长度不符合那么下一根也一定不行51         }52     }53     return false;54 }55 56 int main(void)57 {58     #ifdef LOCAL59         freopen("1455in.txt", "r", stdin);60     #endif61 62     while(scanf("%d", &n) && n)63     {64         sum = 0;65         for(int i = 0; i < n; ++i)66         {67             scanf("%d", &sticks[i].lenth);68             sticks[i].used = false;69             sum += sticks[i].lenth;70         }71         sort(sticks, sticks + n, cmp);72 73         for(int len = sticks[0].lenth; len <= sum; ++len)74         {75             if(sum % len != 0)76                 continue;77             num = sum / len;78             if(DFS(len, 0, 0, 0))79             {80                 printf("%d\n", len);81                 break;82             }83         }84     }85     return 0;86 }
代码君

 


联系
我们