| 比赛场次 | 145 |
|---|---|
| 比赛名称 | 20120706 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-07-06 08:30:00 |
| 结束时间 | 2012-07-06 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 2012暑假培训A班 |
| 题目名称 | 排队 |
|---|---|
| 输入输出 | queuea.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 wo shi 刘畅 |
AATTTTTTTA | 0.000 s | 0.00 MiB | 30 |
 zhangchi |
AWWTTTTTTA | 0.000 s | 0.00 MiB | 20 |
 CC |
ATTTTTTTTA | 0.000 s | 0.00 MiB | 20 |
 Pom |
ATTTTTEETA | 0.000 s | 0.00 MiB | 20 |
 王者自由 |
WWWWWWWTTA | 0.000 s | 0.00 MiB | 10 |
 czp |
AWWWWTTTTW | 0.000 s | 0.00 MiB | 10 |
 fuhao |
AWTWWTTTTW | 0.000 s | 0.00 MiB | 10 |
 Citron酱 |
WWWWWWWWWA | 0.000 s | 0.00 MiB | 10 |
 isabella |
WWWWWWTTTA | 0.000 s | 0.00 MiB | 10 |
 Makazeu |
WWWWWWWWWA | 0.000 s | 0.00 MiB | 10 |
 IMSL77 |
WWWWWWWWWW | 0.000 s | 0.00 MiB | 0 |
【问题描述】
伟大的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