放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

POJ 1011 Sticks​ 题解《挑战程序设计竞赛》

目录

短码之美_页面_001.png挑战程序设计竞赛第二版.jpg

POJ 1011 Sticks 

棒语十级:请将切成不同长度的棒子拚接起来,做出长度相同的棒子,但是要考虑拚接起来的度必须是最短的。换句话说,就是尽量做出更多长度相同的棒子。

举例来说:

hankcs.com 2017-01-20 下午9.43.10.png

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会考虑将输入值(片段的长度)作为顶点,从最幵始的节点开始顺序地建立树形结构(清单)。用图表示就像下面这样。

PKU 1011 Sticks.png

在编写程序之前,先整理一下重点。

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

所谓短码之美

短码之美_页面_001.png

作者还“优化”出一个超级短的版本:

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自动完成的,估计他会有点想法。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1011 Sticks​ 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机