码农场
棒语十级：请将切成不同长度的棒子拚接起来，做出长度相同的棒子，但是要考虑拚接起来的度必须是最短的。换句话说，就是尽量做出更多长度相同的棒子。
举例来说：
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自动完成的，估计他会有点想法。
