数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
' Q8 x' u! p" ~2 |( w% ?) T8 {/ u
输入
" b$ \, e: {9 ^8 e+ y5 G! l
第一行给出n, m, k三个整数。
, x- B$ c# u8 k# j, J
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
6 p" p4 T7 ~) u5 ~! [6 g }
输出
$ I4 k( U& F! s( Q5 I& m8 [& ]7 s
输出仅包括一行，即所求的方案数。
' i& K: E# n u9 n4 `
样例输入
( l" J: Z: `9 N k
3 10 2
2 u D v$ o+ }5 S; B3 {9 F
4 6 8
8 s' K2 h+ {) B0 F
5 2 5
$ E1 t) I4 Y$ f
样例输出
9 t0 K, t, S5 w, I: p& f
4
/ ~ e$ _+ S3 U$ @) V& p# U
Hint
4 j3 P2 \% M1 H% S$ M1 Q. {( C |
数据范围
8 D3 W. X9 Z0 i' B- P* `
对于30%的数据，1 <= n <= 10
& |( O, K/ J0 B
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
4 K6 ^6 b0 h: [; v9 \- `2 g
' L9 _: ]" {6 D7 J
h* ?/ Q; _( F& Q3 B2 F, J
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
9 X b% O/ E' c4 F2 i
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
i; B9 s# t7 I8 `* |$ R
. t/ P! g4 {. L- @9 _
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
# G: e2 o( c% T% S/ w5 ?4 e
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
3 ? ~) W, _# E5 ?7 q
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5