数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
3 K( S/ h5 a- U5 P y9 Q( P
输入
n" O8 F5 `% C
第一行给出n, m, k三个整数。
8 ^. U! @! p& O) n, H
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
& R* O' E: A3 d) S1 ?8 a/ P( T+ H
输出
3 _% s7 Q" C7 e2 O7 l3 c! |
输出仅包括一行，即所求的方案数。
- l/ B$ R/ u C* q% R) Q
样例输入
- h- d1 g; G* R5 \5 M
3 10 2
2 h( R9 }+ X) E" y; y
4 6 8
2 B0 e m: Q1 [9 C! q5 a
5 2 5
) Q5 U0 ?* J d3 i
样例输出
0 K. ~- q' t# z' X. r) H$ T- o( ]4 b5 Y
4
+ U5 }3 n% F1 e
Hint
; X1 c: J' }% S; V) M
数据范围
! L2 a+ f, o" C2 e
对于30%的数据，1 <= n <= 10
5 D3 o1 h2 Y" r6 _/ e0 |8 B
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
+ c; U$ }# i! O: k: f8 @0 Y- \4 C
7 y2 j9 p5 A% }+ F8 Y
- V# Z3 S+ T4 |5 e
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
) G' |) x7 ~7 j( B
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
6 v# M+ q# Q3 S3 N# l4 x
, [# A1 C' X: U. r) c
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
# O- ^: u; h5 ]7 |: ~5 E
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
1 S1 y, [0 ^- K. K) S# A/ @7 e
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5