2011-0035

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by大肥羊

先简单说一下题意：

题目是一个塔防游戏，需要抵抗n个回合的进攻，最开始的时候（即第0回合）玩家拥有一定的金钱，城堡防御为0，每回合要挡住进攻就必须保证当前城堡防御大于等于怪物的攻击力，金币可以用来给城堡加强防御，1个金币可以加强1点防御，每个回合在怪物进攻之前你都有足够的时间用金币来加强防御，抵挡住怪物的进攻【之后】会得到怪物携带的金钱~~

除此之外，玩家还拥有一些农民，每回合这些农民都会收集木材，最初的伐木速率为W，玩家最初没有农民，每个回合结束后玩家可以用金币购买伐木工或者提升伐木效率，每一个伐木工和每提升一点伐木速率的花费是一样的，新购买的伐木工和伐木效率会在下一回合生效

解法就是用两次贪心！

第一个贪心：
首先我们肯定希望每个回合用在防御上的金钱尽量少，那么我们就先假设每个回合怪物进攻之前都不用造防御，如果防御小于怪物的攻击力，那么就用前一天得到的金币来加强防御，还不行就再往前推，直到0回合都不够的话就挡不住了。。这个贪心就是每次都用最近的金币来加强防御，这样越早得到的金币就尽可能的保存下来买农民和伐木速度了，收益明显是最好的

第二个贪心：
上一步做完之后我们会得到每个回合有多少金币可以用，那么这些金币在农民和效率之间怎么分配？很明显农民和效率的和是一定的，而他们的收益是两者的乘积，所以应该尽量让农民和效率之间的差距尽可能小！

代码就不贴了，看了解题报告就自己写写吧

by大肥羊

先简单说一下题意：

题目是一个塔防游戏，需要抵抗n个回合的进攻，最开始的时候（即第0回合）玩家拥有一定的金钱，城堡防御为0，每回合要挡住进攻就必须保证当前城堡防御大于等于怪物的攻击力，金币可以用来给城堡加强防御，1个金币可以加强1点防御，每个回合在怪物进攻之前你都有足够的时间用金币来加强防御，抵挡住怪物的进攻【之后】会得到怪物携带的金钱~~

除此之外，玩家还拥有一些农民，每回合这些农民都会收集木材，最初的伐木速率为W，玩家最初没有农民，每个回合结束后玩家可以用金币购买伐木工或者提升伐木效率，每一个伐木工和每提升一点伐木速率的花费是一样的，新购买的伐木工和伐木效率会在下一回合生效

解法就是用两次贪心！

第一个贪心：

首先我们肯定希望每个回合用在防御上的金钱尽量少，那么我们就先假设每个回合怪物进攻之前都不用造防御，如果防御小于怪物的攻击力，那么就用前一天得到的金币来加强防御，还不行就再往前推，直到0回合都不够的话就挡不住了。。这个贪心就是每次都用最近的金币来加强防御，这样越早得到的金币就尽可能的保存下来买农民和伐木速度了，收益明显是最好的

第二个贪心：

上一步做完之后我们会得到每个回合有多少金币可以用，那么这些金币在农民和效率之间怎么分配？很明显农民和效率的和是一定的，而他们的收益是两者的乘积，所以应该尽量让农民和效率之间的差距尽可能小！

代码就不贴了，看了解题报告就自己写写吧