数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。
" ` j! P/ D" E8 Q% Z8 S
输入
; x) I7 R6 F: S4 t
第一行给出n, m, k三个整数。
( s2 a7 V6 x& u9 ?5 w/ b2 D
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
4 p& G0 `0 C$ X3 O+ z
输出
[2 H$ t" `* l" J+ Q5 X e" d
输出仅包括一行,即所求的方案数。
* n0 N' A1 J+ j9 e
样例输入
) t9 T% ~! H7 d- J$ i3 d* G: }0 L
3 10 2
, E9 n! } O4 L" w% e% K3 T% _1 Y
4 6 8
- A3 `6 s8 e, ~' c/ N* ^2 l" B, N
5 2 5
& V% n( C' g' o* _' ~& t. q$ m! t
样例输出
; p ]2 K9 P8 _5 w
4
- @: h: x+ c D3 [+ r
Hint
3 e R5 h- P8 E9 Y2 A" B
数据范围
/ @- T1 `0 J, H# t+ u, _ s
对于30%的数据,1 <= n <= 10
8 x. Z0 ^3 U' \: z1 n) h9 p
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
2 U! a. v0 \+ w& |5 q
- E8 u# R$ S8 c7 w* O
2 i4 V" e# ^9 @0 \7 p* z
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.
" Q0 T l% m7 y! @0 g: V
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
' t# G2 z. u. ?$ u0 H
' L- _3 g* B: E) \3 g5 e8 A4 F8 G
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
+ b2 k" e. K1 K0 |
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
5 T* x% z- u* A, c7 D/ ^
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5