- 在线时间
- 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的方案数。
0 K9 N; n: K; R- \- { [输入$ S& x3 W9 q, Q
第一行给出n, m, k三个整数。) I3 x7 M' p+ x6 u
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。1 `; ?# B/ d0 I G$ r$ _; B. @+ ?
输出
$ r! E! B* ?4 |+ E) [输出仅包括一行,即所求的方案数。) J2 C4 b! d, D. |
样例输入
, E/ c3 ?% z9 t/ U4 d9 M7 K* O3 10 2
" t& i0 H7 |1 Q1 C9 e& h' m$ v. R4 6 8
6 F) h, O# y1 Y1 _* z0 j0 w5 2 5
6 A4 k7 X9 p1 _$ ]8 b, I样例输出
6 E- G9 u- b6 m% R+ Y4
/ h( T( F5 C g' r, D6 [Hint9 O4 j5 k7 R8 p% X2 t- h
数据范围: s5 @" @+ E, U' S1 B& A# i
对于30%的数据,1 <= n <= 10. J' ~# E) F6 `$ `! P2 M
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。) D7 @7 ~0 I, e2 M. s% K
& u0 i( ]; h& k7 x& o* ]
$ o. c' l( h4 p; h! r& G9 S0 w# G: l我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.( d& y& {# k/ I6 v7 _
或者用动态规划方法,但不知道转移方程怎么写,求大神指点) }3 {' Y) F8 @- Y5 y# o% v
5 g" z: j5 X' A5 o+ R# O7 ?' M/ x |
zan
|