| 题目名称 | 850. 奇怪的棋盘 |
|---|---|
| 输入输出 | boarda.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-07-07加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：6， 提交：29， 通过率：20.69% | ||||
 深绘里 |
100 | 0.043 s | 100.73 MiB | C++ |
 IMSL77 |
100 | 0.456 s | 6.67 MiB | Pascal |
|
IMSL77 |
100 | 0.476 s | 6.67 MiB | Pascal |
|
fuhao |
100 | 1.081 s | 7.90 MiB | Pascal |
 isabella |
100 | 1.644 s | 5.00 MiB | Pascal |
 QhelDIV |
100 | 2.442 s | 23.21 MiB | C++ |
|
QhelDIV |
80 | 0.529 s | 30.84 MiB | C++ |
|
isabella |
80 | 5.329 s | 5.00 MiB | Pascal |
|
QhelDIV |
70 | 3.368 s | 5.82 MiB | C++ |
|
IMSL77 |
70 | 6.176 s | 6.67 MiB | Pascal |
| 本题关联比赛 | |||
| 20120707 | |||
| 关于 奇怪的棋盘 的近10条评论(全部评论) |
|---|
【题目描述】
现在有一张n列的棋盘，每一列的高度为h_i，每一列的底在同一水平线上。
然后你需要在这个棋盘上放k个象棋里的车，使得他们互不攻击，问一共有多少种不同的摆放方法。注意两个车可以互相攻击当且仅当他们处在同一行或者同一列，而且中间的棋盘没有空缺。
上图是一张合法的棋盘，每列高度分别为2，3，1，2，4，而且两个b可以互相攻击，但是a不会互相攻击。
【输入格式】
第一行两个整数，n和k，分别表示棋盘列数和需要放的车的个数
接下来一行n个正整数h_i，表示每一列的高度
【输出格式】
一行一个整数，表示方案数。结果对1000000007取模
【样例输入1】
3 3
2 1 3
【样例输出1】
2
【样例输入2】
5 2
2 3 1 2 4
【样例输出2】
43
【数据范围】
对于40%的数据，0 <= n,k,h_i <= 15
对于70%的数据，0 <= n,k,h_i <= 100
对于100%的数据，0 <= n, k <= 500, 0 <= h_i <= 1000000
【时限】
2s