P1853 投资的最大效益

    • 118通过
    • 295提交
  • 题目提供者 JOHNKRAM 管理员
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 背包 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根据资金总额的增加,更换收益更大的债券。

    题目描述

    例如:有如下两种不同的债券:①投资额$4000,年利息$ 400;②投资额$3000,年利息$ 250。初始时,有$10000的总资产,可以投资两份债券①债券,一年获得$ 800的利息;而投资一份债券①和两份债券②,一年可获得$900的利息,两年后,可获得$ 1800的利息;而所有的资产达到$11800,然后将卖掉一份债券②,换购债券①,年利息可达到$ 1050;第三年后,总资产达到$12850,可以购买三份债券①,年利息可达到$ 1200,第四年后,总资产可达到$14050。

    现给定若干种债券、最初的总资产,帮助约翰先生计算,经过n年的投资,总资产的最大值。

    输入输出格式

    输入格式:

    第一行为三个正整数s,n,d,分别表示最初的总资产、年数和债券的种类。

    接下来d行,每行表示一种债券,两个正整数a,b分别表示债券的投资额和年利息。

    输出格式:

    仅一个整数,表示n年后的最大总资产。

    输入输出样例

    输入样例#1: 复制
    10000 4 2
    4000 400
    3000 250
    输出样例#1: 复制
    14050

    说明

    s≤10^6,n≤40,d≤10,a≤10^4,且a是1000的倍数,b不超过a的10%。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。