5322

P5322 BJOI2019 排兵布阵 基本思路 一眼背包，然后无脑套01，样例也过了，直接提交，40pts。 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace ......

# [BJOI2019] 排兵布阵 ## 题目描述 小 C 正在玩一款排兵布阵的游戏。在游戏中有 $n$ 座城堡，每局对战由两名玩家来争夺这些城堡。每名玩家有 $m$ 名士兵，可以向第 $i$ 座城堡派遣 $a_i$ 名士兵去争夺这个城堡，使得总士兵数不超过 $m$。 如果一名玩家向第 $i$ 座城 ......

## 题目大意 有s名对手，n座城堡，你有m名士兵 如果一名玩家向第 $i$ 座城堡派遣的士兵数**严格**大于对手派遣士兵数的两倍，那么这名玩家就占领了这座城堡，获得 $i$ 分。 求最大得分 ## 数据范围 对于 $10\%$ 的数据： $s=1,n \le 3,m \le 10$ 对于 $20 ......

# P5322 ## 状态表示 $$ dp[i]表示主人公出动i名士兵获得的分数 $$ ## 转移 - 将输入数组进行排序，使得 $in[i][j]$ 表示对于第 $i$ 座城堡，出动兵力第 $j$ 小的玩家的士兵数 - 这样做，如果主人公能在 $i$ 城堡打败第 $j$ 个人，将获得 $i \ti ......

P5322 BJOI2019 排兵布阵 本题主要考察对模型的转化能力。 首先要察觉两条性质： 对于一个城堡，想打败一个玩家的同时用最少的士兵，肯定是正好派出这个玩家在这个城堡派出的士兵数量的二倍加一名士兵。 在一个城堡上，打败了一个在这个城堡派出士兵数量为 $x$ 的玩家，就可以顺便打败所有在这个城 ......