首页 > 其他分享 >H. The Most Reckless Defense

H. The Most Reckless Defense

时间:2024-04-16 21:56:47浏览次数:23  
标签:enemy le cdot cell Most Defense health tower Reckless

H. The Most Reckless Defense

You are playing a very popular Tower Defense game called "Runnerfield 2". In this game, the player sets up defensive towers that attack enemies moving from a certain starting point to the player's base.

You are given a grid of size $n \times m$, on which $k$ towers are already placed and a path is laid out through which enemies will move. The cell at the intersection of the $x$-th row and the $y$-th column is denoted as $(x, y)$.

Each second, a tower deals $p_i$ units of damage to all enemies within its range. For example, if an enemy is located at cell $(x, y)$ and a tower is at $(x_i, y_i)$ with a range of $r$, then the enemy will take damage of $p_i$ if $(x - x_i) ^ 2 + (y - y_i) ^ 2 \le r ^ 2$.

Enemies move from cell $(1, 1)$ to cell $(n, m)$, visiting each cell of the path exactly once. An enemy instantly moves to an adjacent cell horizontally or vertically, but before doing so, it spends one second in the current cell. If its health becomes zero or less during this second, the enemy can no longer move. The player loses if an enemy reaches cell $(n, m)$ and can make one more move.

By default, all towers have a zero range, but the player can set a tower's range to an integer $r$ ($r > 0$), in which case the health of all enemies will increase by $3^r$. However, each $r$ can only be used for at most one tower.

Suppose an enemy has a base health of $h$ units. If the tower ranges are $2$, $4$, and $5$, then the enemy's health at the start of the path will be $h + 3 ^ 2 + 3 ^ 4 + 3 ^ 5 = h + 9 + 81 + 243 = h + 333$. The choice of ranges is made once before the appearance of enemies and cannot be changed after the game starts.

Find the maximum amount of base health $h$ for which it is possible to set the ranges so that the player does not lose when an enemy with health $h$ passes through (without considering the additions for tower ranges).

Input

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$, and $k$ ($2 \le n, m \le 50, 1 \le k < n \cdot m$) — the dimensions of the field and the number of towers on it.

The next $n$ lines each contain $m$ characters — the description of each row of the field, where the character "." denotes an empty cell, and the character "#" denotes a path cell that the enemies will pass through.

Then follow $k$ lines — the description of the towers. Each line of description contains three integers $x_i$, $y_i$, and $p_i$ ($1 \le x_i \le n, 1 \le y_i \le m, 1 \le p_i \le 500$) — the coordinates of the tower and its attack parameter. All coordinates correspond to empty cells on the game field, and all pairs $(x_i, y_i)$ are pairwise distinct.

It is guaranteed that the sum of $n \cdot m$ does not exceed $2500$ for all test cases.

Output

For each test case, output the maximum amount of base health $h$ on a separate line, for which it is possible to set the ranges so that the player does not lose when an enemy with health $h$ passes through (without considering the additions for tower ranges).

If it is impossible to choose ranges even for an enemy with $1$ unit of base health, output "0".

Example

input

6
2 2 1
#.
##
1 2 1
2 2 1
#.
##
1 2 2
2 2 1
#.
##
1 2 500
3 3 2
#..
##.
.##
1 2 4
3 1 3
3 5 2
#.###
#.#.#
###.#
2 2 2
2 4 2
5 5 4
#....
#....
#....
#....
#####
3 2 142
4 5 9
2 5 79
1 3 50

output

0
1
1491
11
8
1797

Note

In the first example, there is no point in increasing the tower range, as it will not be able to deal enough damage to the monster even with $1$ unit of health.

In the second example, the tower has a range of $1$, and it deals damage to the monster in cells $(1, 1)$ and $(2, 2)$.

In the third example, the tower has a range of $2$, and it deals damage to the monster in all path cells. If the enemy's base health is $1491$, then after the addition for the tower range, its health will be $1491 + 3 ^ 2 = 1500$, which exactly equals the damage the tower will deal to it in three seconds.

In the fourth example, the tower at $(1, 2)$ has a range of $1$, and the tower at $(3, 1)$ has a range of $2$.

 

解题思路

  解决这题最关键的地方是要观察到半径 $r$ 最大能取到的值非常小。对于一座具有半径 $r$ 的塔,它最多能造成的伤害为 $\pi r^2 \cdot p_i \leq nm \cdot p_i \leq 50^2 \cdot 500$。又因为在选择 $r$ 后敌人的生命值会增加 $3^r$,因此当 $3^r$ 超过能造成的伤害时,这样的 $r$ 是没有意义的。即 $r$ 应该满足 $3^r \leq 50^2 \cdot 500 \Rightarrow r \leq \log_3{\left( 50^2 \cdot 500 \right)} \approx 12$。

  所以现在的问题是如何把这 $12$ 个不同的半径 $r$ 分配给 $k$ 座塔(不一定要全都选择),使得所有塔能造成的伤害最大。对于每种分配方案,伤害最大值减去该方案增加的生命值就是敌人初始最大能取到的生命值,对每个方案取最大值就是答案。

  可以用状压 dp 来解决。定义 $f(i,j)$ 表示将二进制集合 $j$ 中的半径(第 $i$ 位是 $1$ 表示选择了长度为 $i$ 的半径。没有长度为 $0$ 的半径)分配给前 $i$ 座塔的所有方案中造成伤害的最大值。根据第 $i$ 座塔选择了哪个半径进行状态划分。状态转移方程为:$$f(i,j)=\max\left\{{f(i-1,j),\;\max_{\begin{align*}1 \leq r \leq 12 \\ j(r)=1 \end{align*}}\left\{{f\left(i-1,j \oplus 2^r\right) + s(i,r)}\right\}}\right\}$$

  其中 $j(r)=1$ 表示 $j$ 在二进制下的第 $r$ 位为 $1$。$s(i,u)$ 表示第 $i$ 座塔在半径长度 $r$ 的范围内造成的总伤害,可以通过 $O(k \cdot nm)$ 的复杂度暴力预处理所有的 $s(i,r), \, (1 \leq i \leq k, 1 \leq r \leq 12)$。

  最后答案就是 $\max\limits_{j}\left\{{f(k,j) - \sum\limits_{j(r)=1}{3^r}}\right\}$。

  AC 代码如下,时间复杂度为 $O \left( k \cdot nm + k \cdot 2^r \cdot r \right)$,其中 $r = \log_3{(P \cdot nm)}$,这里直接取成 $12$。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 55, M = N * N, K = 13;

char g[N][N];
LL f[M][1 << K], s[M][K];

bool check(int x1, int y1, int x2, int y2, int r) {    // 计算点(x2,y2)是否在以(x1,y1)为圆心r为半径的圆内
    int dx = x1 - x2, dy = y1 - y2;
    return dx * dx + dy * dy <= r * r;
}

void solve() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%s", g[i] + 1);
    }
    for (int i = 1; i <= k; i++) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        for (int j = 0; j <= 12; j++) {
            s[i][j] = 0;
            for (int u = 1; u <= n; u++) {
                for (int v = 1; v <= m; v++) {
                    if (check(x, y, u, v, j) && g[u][v] == '#') s[i][j] += w;
                }
            }
        }
    }
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < 1 << 13; j++) {
            f[i][j] = f[i - 1][j] + s[i][0];
            for (int k = 1; k <= 12; k++) {
                if (j >> k & 1) f[i][j] = max(f[i][j], f[i - 1][j ^ 1 << k] + s[i][k]);
            }
        }
    }
    LL ret = 0;
    for (int i = 0; i < 1 << 13; i++) {
        LL t = f[k][i], p = 1;
        for (int j = 1; j <= 12; j++) {
            p *= 3;
            if (i >> j & 1) t -= p;
        }
        ret = max(ret, t);
    }
    printf("%lld\n", ret);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    
    return 0;
}

 

参考资料

  Codeforces Round 938 (Div. 3) Editorial:https://codeforces.com/blog/entry/128243

标签:enemy,le,cdot,cell,Most,Defense,health,tower,Reckless
From: https://www.cnblogs.com/onlyblues/p/18139283

相关文章

  • CF1817A Almost Increasing Subsequence 题解
    题面。2023.5.18修正关于前缀和数组的说法,与代码适配的思路。题意给定长度为\(n\)一个序列\(a\)以及\(q\)次询问,每次询问给出\(l\)和\(r\),要求找出序列\(a\)在\([l,r]\)内最长的几乎递增子序列。对于几乎递增的定义:如果一个序列中不存在连续的三个数\(x\),\(y\)......
  • As a reader --> Apollon: A robust defense system against Adversarial Machine Lea
    ......
  • 论文阅读RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection
    文章目录RangeDet:InDefenseofRangeViewforLiDAR-based3DObjectDetection问题笛卡尔坐标结构图Meta-KernelConvolutionRangeDet:InDefenseofRangeViewforLiDAR-based3DObjectDetection论文:https://arxiv.org/pdf/2103.10039.pdf代码:https://......
  • 洛谷 P9907 [COCI 2023/2024 #1] Mostovi 题解
    题目分析首先可以确定的是需要枚举断边,所以我们希望两次枚举之间能有些关联。不难想到类树形DP的套路,建DFS树,只不过这题除了讨论和父亲之间的边,还要考虑返租边。以下钦定以\(1\)为树根。树边先从简单的树边开始考虑。考虑不经过\(u\)和\(u\)的父亲\(v\),对答案是否产......
  • The most influential person
    Inthecenterofanemptystage,amanstoodwithabrownfedorahatandabrownwindbreaker,holdingaredmicrophone.Surroundinghimwasavastredseaoffans.Heslowlyraisedthemicrophone,breakingthesilenceaftertheprevioussongended."......
  • 构建空间场景轻应用,Mapmost Alpha来啦【文末赠书(10本)--第二期】
    文章目录:一、MapmostAlpha介绍二、MapmostAlpha应对数字孪生业务痛点解决之道2.1MapmostAlpha提供海量城市底板2.2MapmostAlpha提供便捷的配置管理工具2.3MapmostAlpha提供一键式部署发布和分享三、沉浸式体验MapmostAlpha3.1创建应用3.2新手指导3.3场......
  • most & least significant bit
    英语是程序员的核心竞争力介绍字节序的wiki中看到一个“mostsignificantbit”的概念,点进去一看还是有点小意思的:原文这里的most/leastsignificantbit从字面上翻译是:最重要的/最不重要的bit。但这个翻译一下子可能不太容易理解:为什么bit还有重要不重要之分?大家日常......
  • 初中英语优秀范文100篇-086The Person Who Has Influenced Me Most-对我影响最大的人
    PDF格式公众号回复关键字:SHCZFW086记忆树1Mymotheristhepersonwhohasinfluencedmemost.翻译我的母亲是对我影响最大的人简化记忆母亲句子结构主语Mymother作为主语,明确指出了影响说话者最大的人是“我的母亲系动词is系动词,用于连接主语和表语,表示主......
  • CF1730F Almost Sorted
    更好的阅读体验CF1730FAlmostSorted挺有意思的一道题。刚看到可能有好几种思路,按照\(p\)的大小填\(q\),或者按照下标顺序填等等。试了几次之后考虑按照\(i\)从小到大填入\(q_i\),设\(pos\)为当前填了的最大的\(p_{q_i}\),由于题目的要求,\(1\sim(pos-m-1)\)的所有数......
  • [ABC279G] At Most 2 Colors 题解
    题目链接题目大意有一个\(1\timesN\)的格子和\(c\)种颜色,每个格子可以染上\(c\)种颜色中的一种。求任意相邻\(k\)个格子染色种类不超过\(2\)种的方案数。思路很明显,这是一个计数DP的题设\(f_i\)表示前\(i\)个格子染色的方案数,考虑第\(i\)个格子的染色情......