数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
0 G$ A1 o2 u, \3 f' s
输入
$ r' d6 K/ G# J N; o
第一行给出n, m, k三个整数。
5 Y' a; A5 b7 y9 q
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
: Y" ^- Z8 V, n! Y
输出
0 Y8 X8 E( i' K" x' f q6 C
输出仅包括一行，即所求的方案数。
9 H/ T% o" P' H( V9 O9 [6 T o1 s4 R
样例输入
5 \8 D' L0 b: I& J: v4 g4 j( B
3 10 2
" e5 c0 k- B' M8 C+ Y2 X* J
4 6 8
4 P4 T) D6 i9 [ ?3 r& Y
5 2 5
1 \) r& h4 Z4 a
样例输出
6 e7 z0 P" x, q
4
0 T8 l F5 j' u" Z0 _& @8 [. w
Hint
- N6 I x7 Z: v' Z/ X. f9 T: ~
数据范围
2 U; q4 |, K3 a# C5 U1 ~
对于30%的数据，1 <= n <= 10
* B9 G$ _8 `+ {5 @0 g7 o8 t1 M u
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
' `! b2 _* t& m' ]! h# K
! o+ e1 K; ~/ E7 s" f
1 N& i7 `+ H0 R9 S0 S V
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
: c. A2 a2 d5 L+ k& c' { ~
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
5 N4 {" {4 M' _2 `- {
& _/ W1 [9 a2 l7 z9 B5 b6 l# n. l
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
& s$ B: U& M# \" d) v% k, h1 J
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
; Y, v0 Y" {/ v, F- O7 I
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5