数学建模社区-数学中国

标题: 一道算法题 k sum [打印本页]

---

作者: Emily_Du    时间: 2016-12-21 12:14
标题: 一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
输入
; x) I7 R6 F: S4 t第一行给出n, m, k三个整数。
( s2 a7 V6 x& u9 ?5 w/ b2 D接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
输出
输出仅包括一行，即所求的方案数。
* n0 N' A1 J+ j9 e样例输入
) t9 T% ~! H7 d- J$ i3 d* G: }0 L3 10 2
4 6 8
- A3 `6 s8 e, ~' c/ N* ^2 l" B, N5 2 5
样例输出
4
Hint
3 e  R5 h- P8 E9 Y2 A" B数据范围
/ @- T1 `0 J, H# t+ u, _  s对于30%的数据，1 <= n <= 10
8 x. Z0 ^3 U' \: z1 n) h9 p对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
2 U! a. v0 \+ w& |5 q

我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
" Q0 T  l% m7 y! @0 g: V或者用动态规划方法，但不知道转移方程怎么写，求大神指点
' t# G2 z. u. ?$ u0 H

---

作者: lshqcable605    时间: 2017-2-4 15:37
6666666666666

---

作者: lshqcable605    时间: 2017-2-4 15:37
8888888888888888
5 T* x% z- u* A, c7 D/ ^

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5