数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
0 g0 }! w: T; n% y I/ X% I
输入
+ s0 Y4 a1 Y& z# E
第一行给出n, m, k三个整数。
8 A; W* T; A( A7 V2 t! `: }
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
# s: A: C3 |9 d' J4 k6 S
输出
2 u' g: A t! ]
输出仅包括一行，即所求的方案数。
8 S+ `8 o! S8 ~& v
样例输入
6 R, G% t4 n! b& P& w8 m4 y5 ^3 T
3 10 2
* z" P) B! x5 C ^2 u& \0 a4 z
4 6 8
- R3 Z* c6 A. |2 ~7 A; X7 w) A
5 2 5
7 B$ L0 v; N! U! @+ F
样例输出
6 v# q2 C7 v3 X1 R' I
4
+ S1 V3 m7 w8 ?8 K/ s. p
Hint
& _& z( N" q0 X5 Y9 V
数据范围
" @0 B* X. }3 o7 H* \/ x4 Q5 Q) k
对于30%的数据，1 <= n <= 10
1 v( A- ^/ N" b1 Y9 ?. w* ]. w
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
$ \! \: w" j& j8 z9 [: ]8 b
' G3 m- X3 a" m: C. P: E
" H) u0 m0 E; v& c H- l
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
8 ^, ?$ Z( g7 G1 F1 l# P
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
# h- b* W" J- ^# T. v2 k3 M0 f
$ F7 u! {. I% [) ~! }5 O4 E' _
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
9 y: x: I5 H5 ^- Y
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
, U! G. O# T. K! T+ r
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5