锐客网

  1. 首页 > it技术 > >

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

动态规划CONTESTS

问题描述

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

    推荐阅读


    上一篇：植物大战数据结构|植物大战 队列 —— 纯C

    下一篇：python|100天精通Python（基础篇）——第30天（标准库random）