一道算法题 k sum

Emily_Du

给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
  X/ z5 d# a) g1 O% Q, ]' N8 C& G2 B输入
第一行给出n, m, k三个整数。
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
输出
4 S% O  I8 l# h& j9 e3 @' c/ W输出仅包括一行，即所求的方案数。
样例输入
5 Q% r( |, M* z. U3 10 2
7 Q' f; e; F) d4 D6 c4 6 8
5 2 5
0 p. J" f- W2 ~" D& a6 Y+ |0 c' @样例输出
4
Hint
数据范围
对于30%的数据，1 <= n <= 10
+ S: r6 [4 L" y3 W# l1 e对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。

- [, [0 P$ [4 J' q
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
' i1 b$ `+ _4 v) Y或者用动态规划方法，但不知道转移方程怎么写，求大神指点
. D6 ^, z7 O4 `

lshqcable605

6666666666666

lshqcable605

8888888888888888
* q" j# L9 A3 }7 ~