P1987 摇钱树

    • 247通过
    • 704提交
  • 题目提供者 lyx613
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Cpg 正在游览一个梦中之城,在这个城市中有n棵摇钱树。。。这下,可让Cpg看傻了。。。可是Cpg只能在这个城市中呆K天,但是现在摇钱树已经成熟了,每天每棵都会掉下不同的金币(不属于Cpg!)。Cpg每天可以砍掉其中一颗,并获得其树上说有的金币(怎么会有这种好事。。。)。请你帮助Cpg算出他在这K天中最多能获得多少金币。

    输入输出格式

    输入格式:

    每个文件中有不超过10组测试数据。

    每组测试数据:

    第一行两个整数n,K (1<=K<=n<=1000)

    第二行n个整数Mi (Mi <= 100000).表示Cpg刚看到这n棵树时每刻树上的金币数。

    第三行n个整数 Bi.(Bi<=1000)表示每颗摇钱树,每天将会掉落的金币。

    以n=K=0结束。

    输出格式:

    对每组测试数据,输出仅一行,Cpg在K天中能获得的最大金币数。

    输入输出样例

    输入样例#1: 复制
    3 3
    10 20 30
    4 5 6
    4 3
    20 30 40 50
    2 7 6 5
    0 0
    
    输出样例#1: 复制
    47
    104
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。