数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
8 |" ^' Y7 K+ G# u3 e: r) X5 v* a
输入
% o, H3 _5 Q! V6 N3 \! F2 r3 A: ^
第一行给出n, m, k三个整数。
5 C# ^3 w7 f# y9 [8 C _# ?, \# E
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
0 R8 H: d# c7 D0 g6 G: L3 g
输出
- v! A$ o0 l; S
输出仅包括一行，即所求的方案数。
5 ]# Z' M. Q4 g) T! z5 R
样例输入
( F+ M0 l+ y o7 L
3 10 2
8 Q" P$ P4 C2 F( O* C2 h* L
4 6 8
% e* Z9 D: U, x! ? Q( r7 L. L
5 2 5
. M& A3 X2 w, A
样例输出
5 Z% T6 `% S2 d$ s/ W+ d9 q1 G# U
4
5 z1 \. v7 _- R) C! o% y
Hint
# F1 e$ a( W% I8 ~2 z: w% [
数据范围
3 I/ @' F! X" b% R9 {" \9 H
对于30%的数据，1 <= n <= 10
3 }4 o% s+ ]/ G
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
- ^6 `0 v5 C9 ]( N2 i r
4 ^8 G% ~3 L N
& p' \8 J8 N# M m
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
, W5 j' g) U0 I$ t2 I. t7 n4 I% ~2 D
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
2 k' _% o1 r! q
# L' n- q. R/ O
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
) ?8 M# g1 V8 h# S
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
: u+ G: k" W1 B1 j% G/ Y- h3 X" x
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5