- 在线时间
- 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的方案数。
3 Z- F4 K; ?. R6 ^1 a输入
# ~! j+ Z) l* h0 s9 {& f第一行给出n, m, k三个整数。& s2 O, y& H9 a) U
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
1 d F: ?7 T: [输出
- E9 J* k+ u- E7 P1 O, s输出仅包括一行,即所求的方案数。- Q+ M) p4 d% @' I4 [8 z
样例输入# s1 K' g4 q( J# \8 T/ Q
3 10 2; ?- S @4 c8 ?: _2 s
4 6 8
}& s* R% M# z O7 C5 2 5/ j) q4 g+ d, z! _9 l0 K
样例输出
& Y* o0 u. [2 J5 j! k48 K. }' K3 r. Z0 {2 E; Z6 [
Hint) P E( }) i; E
数据范围
0 J8 D% O' ]7 O/ f2 s对于30%的数据,1 <= n <= 105 V. z2 Z' ~% A8 m
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。6 w. E" ^4 ^, w
; V! W3 n0 G4 [, H/ K) x- Q7 V3 Q6 |" y* u
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.9 R$ j! v% L5 u1 X7 B% ]2 t; F
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
! R) w1 `; ~6 p% s8 S1 w- l9 g7 h
8 a, @# y0 R& F' G2 } |
zan
|