一道算法题 k sum

Emily_Du

给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
7 l- q# ~+ Q+ V输入
第一行给出n, m, k三个整数。
( F* ^% G8 t+ Q/ K9 I/ `接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
' l# D# h( c8 T' R  \输出
输出仅包括一行，即所求的方案数。
样例输入
" H1 D! y, G( r. x3 10 2
8 \2 O% m7 d$ k. x) p4 6 8
' U" p5 W, b1 J7 P3 D# A& m; q5 2 5
样例输出
4
Hint
0 o5 I% e, j1 t) z, n数据范围
1 K+ `  h3 @7 m, ?, ^9 a9 u对于30%的数据，1 <= n <= 10
& p9 h1 }$ j- u5 G' b对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
* T( [! G- a3 G3 h! m0 V+ Q; l8 P! i
# w, Z2 w/ s3 l5 E5 p( i+ R
. E/ |0 E9 |$ S8 w# I我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
. |" i; D/ d0 T2 `- q9 \5 u或者用动态规划方法，但不知道转移方程怎么写，求大神指点
: p* G' N8 k; q2 w4 q) ]
/ l& ^; {2 W+ l, Q3 D

lshqcable605

6666666666666
% }. B4 C: o# Q2 w: ^. F

lshqcable605

8888888888888888
- o6 ~% G# G% j4 C