QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 9416|回复: 2
打印 上一主题 下一主题

一道算法题 k sum

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

1

主题

10

听众

3

积分

升级  60%

该用户从未签到

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

社区QQ达人

跳转到指定楼层
1#
发表于 2016-12-21 12:14 |只看该作者 |倒序浏览
|招呼Ta 关注Ta
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。2 A& k8 c# F% f% a1 I; F
输入
1 F7 M: R( U( J9 m) H3 B第一行给出n, m, k三个整数。8 h7 [" u/ H6 j3 [
接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
( [3 n; v) B5 y( Q# f输出6 |1 ^1 y: P  `5 R
输出仅包括一行,即所求的方案数。- ~8 D3 v0 v5 P3 Q2 J7 D- |4 V4 `( A
样例输入
' k$ o5 y+ g2 ?9 E0 Q) z3 O3 10 2
  U1 O) d6 w: x" h" h8 x; S4 6 8
) b! G1 c9 R: h2 @9 k( d' i5 2 5- a- D9 M" r# z3 x: |
样例输出
" V0 J; Z) q' @) j4% l+ Y5 N, p6 W( C; B& M
Hint2 f6 z+ g) t1 ?- p
数据范围
' Z# B. N* n3 K, I2 g) |& K对于30%的数据,1 <= n <= 10
' w6 z6 N" {2 Q4 B1 G对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。: w# |- Y% t7 C8 `  H

! @9 l9 s8 s5 ^- J! t$ ~% Q
3 N6 M, \" U# Y. ?1 H我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.) N3 G7 y: L" ^# w, D% F
或者用动态规划方法,但不知道转移方程怎么写,求大神指点* l0 x9 P$ {2 _& o- v

+ s, J6 R7 G2 x3 b
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

4

主题

10

听众

2166

积分

升级  5.53%

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

    [LV.5]常住居民I

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

    群组2016国赛优秀论文解析

    群组2016国赛冲刺培训

    回复

    使用道具 举报

    4

    主题

    10

    听众

    2166

    积分

    升级  5.53%

  • 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, 2026-7-6 08:59 , Processed in 0.374538 second(s), 67 queries .

    回顶部