- 在线时间
- 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的方案数。4 |" B+ d# o& Z$ y% z: Z7 Y8 x
输入: F* i5 L# h1 o4 C, Z$ F' v
第一行给出n, m, k三个整数。+ \. X# X4 f2 b* \: }. R3 M; b
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。, k4 | L- ~0 ~5 u: }
输出
- Y; v; Z7 G3 o输出仅包括一行,即所求的方案数。
2 R: t M' p4 q. u% A样例输入1 f/ q( O! H5 R6 O) f' k; ~
3 10 2( \: }# O# d* B( b" S' [
4 6 8& Y. D( u; D: ]4 ^8 \$ Q, o: N
5 2 5
y! c2 b$ ?# C9 d0 _样例输出
u0 r8 l H, H# f4* a) a( W1 D; `- y) ^2 K/ v
Hint: p0 D! r' c+ ^# \. Z
数据范围
4 x- }( f4 V& F: t l" S对于30%的数据,1 <= n <= 10, Y$ Y! [* q. {1 J! i/ K/ y
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。2 Y5 q. K$ b& V0 h+ K
- E3 t# ?2 g/ X
1 U; f$ R6 ^: s我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.
6 ]. W8 X& ~# R' z或者用动态规划方法,但不知道转移方程怎么写,求大神指点0 G$ m) u& w& I5 | d* E, w
( C8 C, y/ w4 r4 i J- Y% n2 _
|
zan
|