2020-2021:teams:hotpot:atcoderbc176
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:atcoderbc176 [2020/08/28 09:15] lotk |
2020-2021:teams:hotpot:atcoderbc176 [2020/08/28 13:07] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 51: | 行 51: | ||
| 我们显然可以处理出覆盖点最多的行和列，然后依次枚举检查它们交叉的点处有没有点即可，由于点的个数有限，这个检查是符合复杂度的。 | 我们显然可以处理出覆盖点最多的行和列，然后依次枚举检查它们交叉的点处有没有点即可，由于点的个数有限，这个检查是符合复杂度的。 | ||
| + | |||
| + | =====F - Brave Chain===== | ||
| + | |||
| + | ====题目大意==== | ||
| + | |||
| + | 给长度为3n（$n\le 2000$）的序列，每个数都是1到n。每次从前五个里挑三个删除，若这三个数相等，则结果加一。最后剩下的三个若相等，结果也加一。问最终答案的最大值。 | ||
| + | |||
| + | ====解题思路==== | ||
| + | |||
| + | 首先最朴素的思想，是枚举前一次剩下的结果，复杂度$O(n^3)$。随后，发现每次转移的结果，要么是原先的两个，要么是原先的一个加之后的三个中的一个，要么是三个中的两个。后两种一共O(n)种情况，记录一下所有剩余情况的最大mx和所有剩余的里有i的最大$f_i$即可。第一种除非三个全相等，否则结果不变。可以证明，三个全相等时，最优情况一定是删这三个。因此可以单独再用一个数cnt记录这个即可。最终答案为$cnt+max\{mx,dp[a[3n]][a[3n]]\}$。 | ||
2020-2021/teams/hotpot/atcoderbc176.1598577354.txt.gz · 最后更改: 2020/08/28 09:15 由 lotk
