数学建模社区-数学中国
标题:
一道算法题 k sum
[打印本页]
作者:
Emily_Du
时间:
2016-12-21 12:14
标题:
一道算法题 k sum
给定k个整数数列，每组恰好n个，求从每组中选出一个数，它们的和大于m的方案数。
$ @( G. ^$ s+ h+ j* w h
输入
! `0 l2 H" H% f; ^# N0 y2 W" N
第一行给出n, m, k三个整数。
6 _2 G0 ?9 L' G
接下来k行，每行n个整数，表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
5 K6 S& }) g6 E0 L7 N
输出
/ A7 L2 b% k* H' {
输出仅包括一行，即所求的方案数。
& l# \0 ^+ r; z( }+ i& n
样例输入
. a7 r) S% c0 V! \5 Y* r3 y
3 10 2
- I2 a( n+ h Y0 z
4 6 8
: l/ }# @1 C; z
5 2 5
$ e. D# \- A0 H
样例输出
) w \9 q/ `7 V, m( _/ `2 Z9 G" Y2 Q
4
# g5 F! O" g! o9 i
Hint
+ e: J* _4 \; R
数据范围
& q4 f. ~7 G8 z' w1 |
对于30%的数据，1 <= n <= 10
/ i+ e/ g- r3 ~' U+ @8 p
对于100%的数据，1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
* c- ~6 G, q. C" @- ^5 ^
1 ^2 {' G( S8 b+ w7 _
Z' d) y1 g( ~+ d" B0 k1 r
我的思路是，考虑对每个数组先降序排序，然后求每个组合的值是否大于m，这样的话复杂度会比较高，最差情况下是6^100.
7 s/ {0 M- Y! b8 u- z7 Y+ J
或者用动态规划方法，但不知道转移方程怎么写，求大神指点
. w+ C" j& Z9 G6 C+ X& B/ I% @
7 t* A: [. ~# x3 d) U
作者:
lshqcable605
时间:
2017-2-4 15:37
6666666666666
$ J( B( Q# H: Z
作者:
lshqcable605
时间:
2017-2-4 15:37
8888888888888888
- {% ], s8 Z; N. W, ^
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5