| 题目名称 | 849. 排队 |
|---|---|
| 输入输出 | queuea.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-07-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：3， 通过率：0% | ||||
 wo shi 刘畅 |
30 | 7.014 s | 16.39 MiB | Pascal |
 Pom |
20 | 7.551 s | 0.35 MiB | C++ |
|
Pom |
20 | 8.003 s | 4.21 MiB | C++ |
| 本题关联比赛 | |||
| 20120706 | |||
| 关于 排队 的近10条评论(全部评论) |
|---|
【问题描述】
伟大的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