问题描述
何老板喜欢玩植物大战僵尸，在游戏里有一条水平道路，道路的一端是入口，另一端是房子。僵尸会从道路的入口一端向房子一端移动。这条道路刚好穿过N块连续的空地。初始时，僵尸通过每块空地的时间是T秒。玩家可以在这N个空地中种植植物以攻击经过的僵尸，每块空地中只能种植一种植物。
共有三种不同类型的植物，分别是红草、蓝草和绿草，作用分别是攻击、减速以及下毒。每种植物只能在僵尸通过它所在空地的这段时间内攻击到僵尸。
当僵尸经过一块红草所在的空地时，每秒钟生命值会减少R点；当僵尸从一块蓝草所在的空地走出之后，通过每块空地的时间延长B秒；当僵尸从一块绿草所在的空地走出之后，每秒钟会因中毒减少G点生命值。蓝草的减速效果和绿草的下毒效果是可以累加的。也就是说，僵尸通过n块蓝草所在的空地之后，它通过每块空地的时间会变成T+B*n秒；僵尸通过n块绿草所在的空地之后，它每秒钟会因中毒失去G*n点生命值。注：减速和中毒效果会一直持续下去
何老板想知道：怎样在这N块空地里种植各种类型的植物，才能使通过的僵尸失去的生命值最大。输出这个最大值。
输入格式
一行，五个空格隔开的整数N、R、G、B、T
输出格式
一行，一个整数，即通过的僵尸失去的最大的生命值
样例输入
5 4 3 2 1
样例输出
82
提示
30%的数据满足N<=100。
50%的数据满足N<=1000。
100%的数据满足1<=N<=2000;
0 <= R, G, B <= 65536;
0 <= T <= 3。
分析：
首先看到这个题，就想到了动规，状态如下：
f[i][j][k]表示前i个格子，种植j棵绿草和k棵蓝草（i-j-k棵红草），能造成的最大伤害。
方程比较好列，但是时间复杂度为O（n^3）,显然会超时。
那么怎么优化呢？ 一般来讲有以下三种降维优化思路：
（1）最优值法：通过记录上一层的最优值来减少讨论。
2）单调队列：一般是滑动窗口模型。
（3）贪心策略：使状态更具有更大的确定性，达到降维的目的。
本题中(1)(2)的模型都没有出现，那么是否有贪心原则呢？
显然（其实并不），红草一定排在最后。
那么，只需要讨论蓝草和绿草在前面的格子中如何分配就可以了。
状态： f[i][j]表示前i+j格种植i棵蓝草。j棵绿草能造成的最大伤害。
那么红草有p=n-i-j棵。
决策：第 i+j个格子种绿草还是蓝草。
方程：f[i][j]=max{
(1)种蓝草: f[i-1][j]+j*g*(t+b*(i-1));
(i>0)
(2)种绿草: f[i][j-1]+(j-1)*g*(t+b*i);
(j>0)
}
红草区域上造成的伤害为（包括中毒）：p*(j*g+r)*(t+b*i)
边界条件: 0<=i<=n 0<=j<=n i+j<=n
时间复杂度O(n*n),需要使用滚动数组优化空间。
代码如下：
#include
#include
#include
#define LL long long
using namespace std;
const int maxn=2000+5;
LL n,r,g,b,t,f[3][maxn];
int main(){
LL i,j,ans=0;
cin>>n>>r>>g>>b>>t;
for(i=0;
i<=n;
i++)
for(j=0;
j+i<=n;
j++){
LL p=n-i-j,red;
red=p*(j*g+r)*(t+b*i);
//红草区域上的伤害值
f[i&1][j]=0;
//使用滚动数组时千万要注意清零
if(i>0) f[i&1][j]=max(f[i&1][j],f[!(i&1)][j]+j*g*(t+(i-1)*b));
//种蓝草
if(j>0) f[i&1][j]=max(f[i&1][j], f[i&1][j-1]+(j-1)*g*(t+b*i));
//种绿草
ans=max(ans,f[i&1][j]+red);
//cout<<"f("<
推荐阅读
- 蓝桥杯|蓝桥python——方格分割【2017 第四题】
- 算法|不会有人2022年还不懂栈吧（）
- 《力扣周赛题解》|【解题报告】力扣 第 277 场周赛
- 动态规划|AcWing 271. 杨老师的照相排列（简单DP）+ 十一届蓝桥杯B组试题E--矩阵
- 蓝桥杯练习题|分解质因数
- 动态规划|LeetCode 300.最长递归子序列
- 菜鸟刷题|蓝桥杯每日一题——最大字段和问题（动态规划）
- 《力扣周赛题解》|【解题报告】力扣 第 279 场周赛
- 备战蓝桥杯|【蓝桥Python每日一练】————砝码称重（状压DP）