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

QQ登录

只需要一步,快速开始

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

一道算法题 k sum

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

1

主题

10

听众

3

积分

该用户从未签到

升级  60%

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

社区QQ达人

发表于 2016-12-21 12:14 |显示全部楼层
|招呼Ta 关注Ta
给定k个整数数列,每组恰好n个,求从每组中选出一个数,它们的和大于m的方案数。, R! A. c# B/ d# k8 K* Q: ~5 {9 C1 I
输入. T! h  C7 [# R, J' H* F% }) `
第一行给出n, m, k三个整数。
) J7 ]/ R! `! w, k接下来k行,每行n个整数,表示这个数列中的所有元素。数列中每个元素为不超过10^7的正整数。
( \0 j( \9 Q4 [' a; E8 \输出, z7 D1 g  F( t9 o( A% N+ s+ C2 F  e
输出仅包括一行,即所求的方案数。7 k, K% J! ?6 t' x$ E
样例输入
/ Z% _2 V9 G8 p$ R3 10 2& w( G; b8 e1 Q# F2 r3 C. M7 \$ ^
4 6 8
; }; a7 p/ {- u% ?5 2 5
& j! R( D0 |, |8 \6 [样例输出
/ j9 X( Y7 ^/ N4 Y4' z7 _, V* {, f" M
Hint1 U, z/ I8 r) `; X* U# v7 Q, ~* o
数据范围3 S9 `& q4 w% V+ M( T0 l  ?" ]1 Z
对于30%的数据,1 <= n <= 10
2 A% G4 ]4 j7 U6 I6 X- H0 }对于100%的数据,1 <= n <= 100, 1 <= m < 2^31, 1 <= k <= 6。$ p: @7 H7 x5 P

1 U! z+ ?1 s- G' V! W# H
# Q0 m. ]# Y& r2 o. [: {我的思路是,考虑对每个数组先降序排序,然后求每个组合的值是否大于m,这样的话复杂度会比较高,最差情况下是6^100.' n$ b/ }9 J; K* D; n3 Q
或者用动态规划方法,但不知道转移方程怎么写,求大神指点
+ S) D- h* w7 R1 x5 z2 e# g
9 y- ?! d! g, D9 Q6 z' _
zan

4

主题

10

听众

2172

积分

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

    [LV.5]常住居民I

    升级  5.73%

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

    群组2016国赛优秀论文解析

    群组2016国赛冲刺培训

    回复

    使用道具 举报

    4

    主题

    10

    听众

    2172

    积分

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

    [LV.5]常住居民I

    升级  5.73%

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

    群组2016国赛优秀论文解析

    群组2016国赛冲刺培训

    回复

    使用道具 举报

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

    fastpost qq
    收缩
    • 电话咨询

    • 04714969085

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

    手机版|Archiver| |繁體中文   

    蒙公网安备 15010502000194号

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

    GMT+8, 2019-10-15 09:45 , Processed in 1.037471 second(s), 69 queries .

    回顶部