排队

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 queuea.in 输出文件 queuea.out

【问题描述】

伟大的Farmer John要来jzyz签字卖书了。Jzyzoier都怀着激动的心情排队去买书。

作为一件伟大的事情,排队的方式当然不能太简单了。

排队的第一原则是和谐, oier都很兴奋,组织者发现如果某些相邻oier很熟悉,他们就会大声说话,他们说话的声音与他们熟悉程度成正比,这样就很影响Farmer John签字的心情。所以我们要让队伍中所有相邻的两个人之间的熟悉程度总和最小。

为了不让队伍过于凌乱,排队时还要满足以下规则:每个人都有固定的身高H[i],给定一个高度差K,如果H[a]-H[b]大于等于K,那么第a个人必须在第b个人的后边。

此外,为了简化问题,最矮的人将被排在队头。

现在给定所有人的熟悉程度,求出满足高度差的情况下,整个队伍的最小熟悉程度总和。

【输入】

第一行两个整数NK,表示总人数和允许的高度差K

接下来一行是递增的N个整数,表示N个人的高度H[i]

接下来N*N的整数矩阵WW[i][j]表示第i个人和第j个人的熟悉程度,当然W肯定是对称的,且对角线的值肯定是0.

【输出】

一个整数,整个队伍的最小熟悉程度总和

【输入输出样例1

queuea.in

queuea.out

5 8

1600 1601 1604 1607 1609

0 0 53 33 37

0 0 39 0 20

53 39 0 56 2

33 0 56 0 36

37 20 2 36 0

38

【样例解释】 最优的排队顺序是 1600 1601 1607 1609 1604

【数据范围】 

   对于20% 数据  1<=N<=10

对于50% 数据  1<=N<=100

   对于40%数据   1<=K<=4

对于100% 数据  1<=N<=1000  1<=K<=8  1000<=H[i]<=5000