数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
4 H8 h( N+ X7 @0 Z. [% ^
输入
l5 c2 s& ^' a5 d
第一行给出n, m, k三个整数。
0 e1 l' s% h, n
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
. {. a$ o% o8 U' K. ?. E- l6 }
输出
. A% z2 k- A9 s7 h7 U
输出仅包括一行，即所求的方案数。
4 @& O5 P+ F$ Q1 _& L5 N
样例输入
8 B' s# R$ \1 x. B" a7 _
3 10 2
* x9 G0 G3 N- _5 v ?: z7 m9 i
4 6 8
4 j7 v1 w+ C0 E5 R/ f
5 2 5
1 G5 F% G& g& B( V" H; k' i7 b
样例输出
; M5 I; j3 \% [. ]% B; ?& ^
4
) c/ U* l$ l0 J
Hint
/ j1 L, A) ]- ^8 G
数据范围
+ k% z+ P( M3 M, r* I2 M0 m
对于30%的数据，1 <= n <= 10
9 A6 z6 J2 A E- G! }' D. j; N: B
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
2 a( U3 u U+ I% ~& \- w3 `1 G
; x: w0 V: r; c4 |. {8 v7 c! Y
4 N/ [/ l5 L" x
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
* v% S+ G( e9 H/ R4 ]( Z
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
; o' s! w5 q8 C4 J" {( d0 v
# A+ z, }7 d5 h3 y- @
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
6 x& T- e% z- H: `
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
* R# U, P$ Q7 q& F1 F
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5