- 在线时间
- 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的方案数。% I6 b$ ]4 C* {) F& e0 R
输入* J7 Z" L: e6 X' \
第一行给出n, m, k三个整数。
) Z# E! ~6 Q- u1 q2 f# v" j8 R接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。. P% I6 |: S8 R# {/ S2 o( {
输出8 \ I7 r \! w0 B( ]
输出仅包括一行,即所求的方案数。
4 I/ O# ~0 i! O3 y2 t( n. K& W1 J7 b样例输入/ D' T% z3 W% f' n3 R! r$ l. c
3 10 23 A5 I; Z4 d' j: s( v0 s
4 6 86 @ P' Q# U) a- m9 s8 \) j
5 2 5
/ R/ p0 V2 n: X样例输出9 E* u) G) q& z5 |/ g0 H
43 g' N# P- a; m2 G3 n* u1 m/ f- b
Hint8 C% z( J1 w* z/ W0 _" \8 i
数据范围
; y1 A/ I* [* `/ Y2 ?对于30%的数据,1 <= n <= 101 Z( R5 X# L: H7 Q* }
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
) ^# b# Y0 p Y) J- t$ u6 S M/ e
8 U: C' _" J# E: `6 D `* c0 E7 V, F/ e$ Z. |
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100., X: _! b0 @. W8 \; ~
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
$ q- U5 Y Q" Z+ j9 M, v% n. z6 q2 f) R" Y) N/ `
|
zan
|