棒语十级:请将切成不同长度的棒子拚接起来,做出长度相同的棒子,但是要考虑拚接起来的度必须是最短的。换句话说,就是尽量做出更多长度相同的棒子。
举例来说:
4.5开动脑筋智慧搜索
剪枝
看到《短码之美》上有,那就直接看书吧。
如果是简单地输入,即使做了一些无谓的搜索,也能够求出结果。但是,由于切出来的段数最多有64根,单纯计算所有组合就需要很长时间。这次用一个稍微复杂一点的例子,首先手动求组合看看。
首先,准备下面这样的测试数据。
8 3 8 15 2 11 4 8 1
这9个数值的合计(sum)是60,最大值(max)是15,60的约数中比15大的有15、20、 30、60(=length)这4个,检查切出来的全部片段是不是能够拼出这些长度的棒子。
首先考虑length=15的情况。
将这9个数字降序排列:
15 11 8 8 8 4 3 2 1
从这个清单的开头开始,分割成合计为15的部分。
15
11,4
8,…
15保持原状,下一个11+4=15,再下一个8加上8就是16 了,超出了 15。即使依次加上3、 2、1还是等于14,凑不上15。所以知道原本棒子的长度不是15。那么下面这组又怎么样呢?
15
11,3, 1
8,…
同前面那组一样无法凑成15,似乎原本棒子的长度不是15。 20能行吗?
15, 4, 1
11,8,…
最初选择{15, 4, 1}就不能拼出第2根棒子了,但是这就说20不行有些太早了。
15,3,2
11,8, 1
8, 8, 4
如果最开始的一组用{15, 3, 2},就能顺利凑齐长度是20的棒子。接下来把这样的搜索方法用程序代码来实现就可以了。怎样做才好呢?
前面是手动来检査搜索方法,现在可以通过DFS算法来实现。DFS会考虑将输入值(片段的长度)作为顶点,从最幵始的节点开始顺序地建立树形结构(清单)。用图表示就像下面这样。
在编写程序之前,先整理一下重点。
1、将数椐按降序排序。
2、从数值最大的开始(=从数组开头幵始),依次减去K度值,直到棒子的长度(length)
变成0为止,同时标记用到的数值。
3、如果长度变成0,则把length恢复原值,再执行②。
4、如果失败,则返回到前一个状态。
5、如果做出sum/length个长度是length的棒子就成功了。
#include <iostream> using namespace std; int in[51]; //长度为i的片段个数 int length; //棒子的原始长度 int finish; //终止标志(非0即终止) /** * 遍历 * @param count 棒子的总数(如果为0,则结束) * @param len 目前检查的棒子长度的剩余量 * @param plen 现在检查的片段长度 */ void check(int count, int len, int plen) { --in[plen]; //取一个长度是plen的片段来用 if (count == 0) finish = 1; if (!finish) { len -= plen; if (len != 0) { int next_plen = min(len, plen); //剪枝策略:用plen去凑len,next_plen必须是较小者 for (; next_plen > 0; --next_plen) if (in[next_plen]) //有剩余 check(count, len, next_plen); } else { //片段长度最大为50 int max = 50; while (!in[max]) --max; check(count - 1, length, max); } } ++in[plen]; //恢复原始状态 } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int n; while (~scanf("%d", &n) && n) { memset(in, 0, sizeof(in)); int sum = 0; int max = 0; finish = 0; while (n--) { int b; scanf("%d", &b); ++in[b]; sum += b; if (max < b) max = b; } length = max; while (true) { if (sum % length == 0) check(sum / length, length, max); if (finish) break; ++length; } printf("%d\n", length); } #ifndef ONLINE_JUDGE fclose(stdin); #endif }
16505022 |
hankcs | 1011 | Accepted | 164K | 16MS | C++ | 1555B | 2017-01-21 11:37:14 |
所谓短码之美
作者还“优化”出一个超级短的版本:
L,F,*I; c(n,l,p,j){ --I[p]; for(j=l-=p;F*j;--j)I[j]&&c(n,l,j); for(j=F=--n?F:0;!I[j];)--j;l||c(n,L,j); ++I[p]; } main(s){ int w[999]={s=F}; for(scanf("%d",I=w);w[0]--;++w[L],s+=F<L?F=L:L)scanf("%d",&L); for(L=F-1;F;s%++L||c(s/L,L,F));s&&main(printf("%d\n",L)); }
短倒的确是短,可是真的美吗?
我的确很钦佩日本人变态的工匠精神,但耗费那么多时间研究各大编译器的奇巧淫技,最终只换来代码可读性的巨幅下降,窃以为走错路了。除了这个小“亚文化圈”,估计没有任何开源社区、企业团队能够接受这种类似于“密码”的源码。
追求短必然会减小变量名、函数名长度,减少注释、缩进、大括号……任何一点,对代码可读性都是毁灭性的打击。
另外如果作者知道前端开发中JavaScript有一个uglify的工序,而该工序是由compressor自动完成的,估计他会有点想法。