请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 7557|回复: 2

一道算法题 k sum

[复制链接]
字体大小: 正常 放大
Emily_Du        

1

主题

10

听众

3

积分

升级  60%

该用户从未签到

自我介绍
算法爱好者,数学建模爱好者

社区QQ达人

发表于 2016-12-21 12:14 |显示全部楼层
|招呼Ta 关注Ta
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。% I6 b$ ]4 C* {) F& e0 R
输入* J7 Z" L: e6 X' \
第一行给出n, m, k三个整数。
) Z# E! ~6 Q- u1 q2 f# v" j8 R接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。. P% I6 |: S8 R# {/ S2 o( {
输出8 \  I7 r  \! w0 B( ]
输出仅包括一行,即所求的方案数。
4 I/ O# ~0 i! O3 y2 t( n. K& W1 J7 b样例输入/ D' T% z3 W% f' n3 R! r$ l. c
3 10 23 A5 I; Z4 d' j: s( v0 s
4 6 86 @  P' Q# U) a- m9 s8 \) j
5 2 5
/ R/ p0 V2 n: X样例输出9 E* u) G) q& z5 |/ g0 H
43 g' N# P- a; m2 G3 n* u1 m/ f- b
Hint8 C% z( J1 w* z/ W0 _" \8 i
数据范围
; y1 A/ I* [* `/ Y2 ?对于30%的数据,1 <= n <= 101 Z( R5 X# L: H7 Q* }
对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。
) ^# b# Y0 p  Y) J- t$ u6 S  M/ e
8 U: C' _" J# E: `6 D  `* c0 E7 V, F/ e$ Z. |
我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100., X: _! b0 @. W8 \; ~
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
$ q- U5 Y  Q" Z+ j9 M, v% n. z6 q2 f) R" Y) N/ `
zan

4

主题

10

听众

2167

积分

升级  5.57%

  • TA的每日心情
    开心
    2017-9-19 17:40
  • 签到天数: 59 天

    [LV.5]常住居民I

    群组数学中国美赛辅助报名

    群组2016国赛优秀论文解析

    群组2016国赛冲刺培训

    回复

    使用道具 举报

    4

    主题

    10

    听众

    2167

    积分

    升级  5.57%

  • TA的每日心情
    开心
    2017-9-19 17:40
  • 签到天数: 59 天

    [LV.5]常住居民I

    群组数学中国美赛辅助报名

    群组2016国赛优秀论文解析

    群组2016国赛冲刺培训

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2024-3-29 06:30 , Processed in 0.550524 second(s), 70 queries .

    回顶部