- 在线时间
- 0 小时
- 最后登录
- 2016-12-21
- 注册时间
- 2016-12-21
- 听众数
- 10
- 收听数
- 0
- 能力
- 0 分
- 体力
- 8 点
- 威望
- 0 点
- 阅读权限
- 10
- 积分
- 3
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 1
升级   60% 该用户从未签到 - 自我介绍
- 算法爱好者,数学建模爱好者
 |
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。( ~8 o7 W0 {' o( t
输入3 b2 q E6 b: Y+ v0 Y. j
第一行给出n, m, k三个整数。0 t/ s" q# E# J/ g2 r4 m$ m& v
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
" b9 u1 d; n- s. z' I, y( U输出/ N( Z- x+ ~% }3 v9 G
输出仅包括一行,即所求的方案数。
* E: Z8 f Q: k+ s+ q7 Y0 T样例输入- T: k" _, n0 V
3 10 20 }) j5 B% g5 _- n
4 6 8
/ g- V( K/ A- {' h7 \5 2 5+ o# e4 z% P9 E2 i7 z5 E+ T
样例输出4 e2 F/ O7 b( E+ d
4. m7 o8 m. l0 a2 r5 ~
Hint
) m0 z* O. a: X6 W) |% R1 J数据范围
" n% L1 N, h/ H$ }对于30%的数据,1 <= n <= 106 e* L" J/ W+ Z; t! J- B! ?
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。7 q2 l: a' w$ L2 A
9 D8 t5 ]' ^# k
# w* |1 X! P- n+ ^- t/ r5 {
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.
) L4 ?; b! @+ S% X! v- X或者用动态规划方法,但不知道转移方程怎么写,求大神指点* s9 P+ p$ x3 J* I h( L
- z: o5 {# x# I: r
|
zan
|