动态规划|dp+贪心+滚动数组优化——植物大战僵尸

问题描述

何老板喜欢玩植物大战僵尸,在游戏里有一条水平道路,道路的一端是入口,另一端是房子。僵尸会从道路的入口一端向房子一端移动。这条道路刚好穿过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("<

    推荐阅读