我：08
08
CF1955H
塔防游戏，游戏有 \(n\times m\) 的地图，地图上已经有 \(k\) 座塔，并给出敌人从 \((1,1)\) 移动到 \((n,m)\) 的路径，敌人每秒移动一格，恰好遍历完这个路径；一秒内若敌人在 \((x,y)\)，而一个塔 \(i\) 满足 \((x-x_i)^2+(y-y_i)^2\le r_i^2\)，则敌人收到 \(p_i\) 伤害；若敌人在途中生命值 \(\le0\) 则你胜利，你可以给每个塔设定 \(r_i\) 为正整数，但是此时敌人初始血量 \(h\) 也将增加 \(3^{r_i}\)，且要求所有 \(r_i\) 互不相同。你需要找到 \(h\) 的最大值使有可能通过设定 \(r_i\) 让你获胜；若不可能获胜输出 0，\(n,m\le50,1\le p_i\le500\).
01
给出 \(n\) 个基本法术和 \(m\) 个复合法术以及怪兽的初始血量 \(hp\)，每个基本法术可以给怪兽 \(b_i\) 的血量变化值，每个复合法术可以由基本法术以及其他复合法术组成，保证引用关系是个 DAG，现施展最后一个复合法术，问若怪兽被杀死，是哪个基本法术杀死他的；或者回答不能杀死，\(n,m\le5000,1\le hp\le10^9,|b_i|\le10^9\).
Solution
08
首先若没有 \(r_i\) 互不相同的限制，则各个防御塔之间没有关系，可以贪心每个 \(r\) 最大的
现在加上这个限制，发现可以 dp
首先有性质：\(r\le12\)，因为要让 \(3^{r_i}-cnt_i\cdot p_i\le0\)，即 \(3^{r_i}\le cnt_i\cdot p_i\le2500\times500\)，有 \(r_i\le\log_3(2500\times500)\)，故有 \(r\le12\)
然后很典的状压 dp，一维是每个 \(r\) 分别有没有被用过
01
对每个法术计算施展过程中，敌人血量的最小值（前缀和的 \(\min\)），以及施展完成对敌人血量的总伤害，然后做完了.
标签：le,每个,记录,08,血量,法术,敌人 From： https://www.cnblogs.com/laijinyi/p/18544605