hdu4939思维DP
题目
在坐标轴$[1,n]$上,每两个相邻的整数点之间可以放置一座防御塔。
怪物初始时 $t$ 秒移动一个单位。
防御塔$1$:在当前线段上的敌人每秒受到$x$伤害。例如在$[1,2)$上放置一座防御塔$1$,怪物在$[1,2)$上行走每秒会受到$x$伤害。
防御塔$2$:在当前线段后的敌人每秒受到$y$伤害。例如在$[1,2)$上放置一座防御塔$2$,怪物在$[2,n)$上行走每秒会受到$y$伤害。
防御塔$3$:在当前线段后的敌人被减速$z$。例如在$[1,2)$上放置一座防御塔$3$,怪物在$[2,n)$上行走会被减速$z$,也就是$t=t+z$。
防御塔2/3的效果可以叠加。
数据范围 (2<=n<=1500 , 0<=x,y,z<=60000 1<=t<=3)
问一个敌人从$1$走到$n$受到的最大伤害是多少。
解题思路
经过一点分析,显然有防御塔1肯定是连续的放置在最后面一段区间。
令$DP[i][j]$为前$i$个防御塔,放置$j$个防御塔$2$、$i-j$个防御塔$3$的最大伤害,$i$后面全为防御塔$3$。这时候,前面防御塔2/3的排列顺序对后面的贡献无影响。只记录数量即可。
因此有状态转移方程:
1 | dp[i][j] = dp[i-1][j] + V1; |
AC代码
1 |
|