PID482 / 完美的牛奶
题目描述

牛奶是一种很富有营养的饮品。但是,不同组成的牛奶所包括的营养是不一样的,为了喝到最富有营养的牛奶,我们需要自己产奶。当然,这里的产奶指的是我们对牛奶进行二次加工。

已知,我们的牛奶中包含有N个不同的基因,而每个基因又是由不同的物质组成的,为了让牛奶的的营养度达到最大,我们将对其进行加工。

牛奶的基因个数我们是无法改变的,但是我们可以改变每个基因的权值,而每个基因的权值是由你来决定的,即选择一个物质,来作为它的主要组成物质,然后基因的权值就是这个物质的权值。最后我们加工成的牛奶,就变成了一个具有N个权值的序列配方。

然后,这个牛奶的营养度是这样定义的,即相邻两个基因的差的乘积的绝对值。这样,营养度越高越好,你所需要做的,就是找出这样一个牛奶序列配方,使其营养度最高。

输入格式

第一行,一个数,N,即牛奶所含的基因数。

以下N行,每行第一个数是T,即这个基因的构成物质数量,紧跟着T个数是该基因的每个组成物质的权值C,且按升序排列。

30%

2≤N≤10

1≤T≤10

C≤100

100%

2≤N≤100

1≤T≤50

C≤1000

输出格式

第一行,为最高的营养度。

第二行,为具有最高营养度的牛奶序列配方。(若有不同解,则使最后一个基因权值最小,若还有不同解,则取倒数第二个基因权值最小,依次类推)

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论