题目内容

小美是一个喜欢种田类的游戏的人，他觉得这样的游戏可以让他体验到农民的乐趣，同时也可以锻炼他的经营能力。他最近在玩一个叫做“农场大亨”的游戏，这个游戏的目的是在有限的时间内赚尽可能多的钱。游戏中有 $n$ 种作物，每种作物都有自己的特点，比如生长周期、种子成本、作物收益等。小美需要根据这些信息，合理地安排自己的种植计划，以达到最大化利润的目标。

小美只有一块土地，也就是说每个时间只能由一个作物在生长。他需要在游戏开始时购买种子，然后种植在土地上。种子的买入价格为 $a_i$ ，作物卖出价格 $b_i$ 。一个种子只会产出一个作物，种子可以重复购买。第 $i$ 种作物从种植到作物成熟采摘需要 $t_i$ 天时间，种植和采摘、卖出等操作不耗时间，成熟之前作物没有价值。如果小美想要更换作物，他需要先把当前作物采摘卖出，然后再购买新的种子。

游戏内总时长为 $m$ 天，也就是说小美只有 $m$ 天的时间来经营自己的农场。小美初始的钱足够多，不用担心资金不足。小美想知道，在这样的条件下，他最多能赚多少钱。

输入描述

第一行两个整数 $n$ ， $m$ $(1 \leq n , m \leq 1000)$ 表示作物种类数和游戏时长；

第二行 $n$ 个正整数，表示每种作物的成熟时长 $t_i(1 \leq t_i \leq m)$；

第三行 $n$ 个正整数，表示每种作物的种子价格 $a_i(1 \leq a_i \leq 100000)$；

第四行 $n$ 个正整数，表示每种作物的卖出价格 $b_i(a_i \leq b_i \leq 100000)$ 。

输出描述

输出一个整数来表示小美最多能赚的钱。

样例1

输入

3 12
3 4 7
9 3 2
11 6 11

输出

12

样例解释

赚钱最多的方案是先种一个第二种作物，然后种一个第三种作物，耗时 $4+7=11$ 天，赚的钱数为 $6-3+11-2=12$ ，可以证明这是最优的方案。

样例2

输入

10 100
81 21 66 63 48 25 23 88 71 65
56 12 94 57 57 6 37 63 87 64
62 68 99 93 88 96 47 65 97 69

输出

360

思路:动态规划-完全背包

对于每种作物，如果种下之后不收获，那么这段时间就是会被浪费的，所以每种作物我们考虑其赚的钱和需要付出的时间。 同时可以重复种同一种作物，那么这就是一个完全背包问题。总游戏时长就是背包容量，单个作物从种下种子到收获卖出的时间就是物品体积，赚到的钱就是物品的价值。

知识点学习:动态规划

1.动态规划(dp)入门 by 一只会code的小金鱼

推荐理由:由浅入深,从dfs -> 记忆化搜索 -> 动态规划 的思路来讲解dp。也是公认的比较符合人类思维的理解dp的过程。