网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
排队
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | queuea.in | 输出文件 | queuea.out |
【问题描述】
伟大的Farmer John要来jzyz签字卖书了。Jzyz的oier都怀着激动的心情排队去买书。
作为一件伟大的事情,排队的方式当然不能太简单了。
排队的第一原则是和谐, oier都很兴奋,组织者发现如果某些相邻oier很熟悉,他们就会大声说话,他们说话的声音与他们熟悉程度成正比,这样就很影响Farmer John签字的心情。所以我们要让队伍中所有相邻的两个人之间的熟悉程度总和最小。
为了不让队伍过于凌乱,排队时还要满足以下规则:每个人都有固定的身高H[i],给定一个高度差K,如果H[a]-H[b]大于等于K,那么第a个人必须在第b个人的后边。
此外,为了简化问题,最矮的人将被排在队头。
现在给定所有人的熟悉程度,求出满足高度差的情况下,整个队伍的最小熟悉程度总和。
【输入】
第一行两个整数N和K,表示总人数和允许的高度差K。
接下来一行是递增的N个整数,表示N个人的高度H[i]。
接下来N*N的整数矩阵W,W[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