数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
" D A% J2 c$ v) @2 Z/ I7 [
输入
5 L3 f( \8 y1 O) \; z" y, L
第一行给出n, m, k三个整数。
0 G1 M" j' l" L1 s9 K8 P
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
( I! Z/ M9 }7 k: ]1 t- Q
输出
" b: z0 Z: h: C# E5 ~( X
输出仅包括一行，即所求的方案数。
1 u/ T/ N7 z/ p0 H3 N8 ?
样例输入
+ c- z- s& g2 V. O/ @
3 10 2
( c; I/ U* h3 L6 d) }; Z
4 6 8
# ?4 _# R9 L: m) L4 y2 X
5 2 5
f' o' e# z) }( W" t
样例输出
5 R" K+ G/ V9 p3 R/ {* f
4
- ~( |2 x' L* S- m8 P ~( M& k
Hint
6 ]6 R( g G+ K/ c5 b O3 C
数据范围
# d3 T$ ?9 F1 v3 D6 E9 X# }- M
对于30%的数据，1 <= n <= 10
- q6 t% b; {, |2 S# x$ T
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
5 c. d* f" D7 z8 m7 a7 t
: r, e% Z+ ]0 \8 \4 g
" l2 J" j7 k7 r; Q
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
" C: |1 u. F& ^3 ~
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
4 T5 d5 y2 Y( b
" s0 E% o h: D: q5 x
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
3 }: g, w8 e; h0 x# ~% z# W$ o
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
# l* X3 `7 y* b. }* V) N
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5