- 在线时间
- 0 小时
- 最后登录
- 2016-12-21
- 注册时间
- 2016-12-21
- 听众数
- 10
- 收听数
- 0
- 能力
- 0 分
- 体力
- 8 点
- 威望
- 0 点
- 阅读权限
- 10
- 积分
- 3
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 1
升级 60% 该用户从未签到 - 自我介绍
- 算法爱好者,数学建模爱好者
|
发表于 2016-12-21 12:14
|显示全部楼层
|
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。, W0 ~1 v" d2 I2 L& ]& [# A+ T
输入8 [) I7 k- g% R' U
第一行给出n, m, k三个整数。
/ q7 D7 w, O& R9 } H+ \& l( r Y0 p接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。; d$ {; y7 t5 M( ]0 z: u
输出9 O) s3 W: {7 z {: C$ j/ B) u
输出仅包括一行,即所求的方案数。
8 t8 b$ f* j9 g) X0 C* F# t+ e4 p4 d6 I样例输入
: I2 U' N, e6 }+ r6 _- \/ m& P3 10 2
8 m# B4 ?. y+ r: z/ l9 l# w4 6 8
: _) f; Q9 v! z6 b4 t9 q6 ?+ B9 C5 2 5+ \$ X1 v& ^+ n3 w7 ?7 C7 y
样例输出5 G+ }5 Q9 c; A
4
; K7 L5 t2 e! ?# y$ w* \: OHint# S( f" L$ ]8 d- C3 n6 R5 t
数据范围
5 M0 o6 k2 E6 A! c" T; G0 f对于30%的数据,1 <= n <= 10" p' U. e6 a; @( q8 r
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。3 ]* v! x8 ]/ s8 Y9 ?
7 j! J- l/ c4 D% w" _! d2 B+ ]1 Z1 v; C! r
& e; O. y$ s3 _5 W; j+ @
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.) L) P& v3 A W: ?% S
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
; O9 J2 f* T+ v3 h# W" o
) _5 j' f2 I# @, J( y |
zan
|