主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF1110D Jongmah
最后更新于 2025-08-28 08:54:30
作者
2huk
分类
题解
题解
CF1110D
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
显然输入顺序是无所谓的。首先用个桶统计每个数的出现次数。 注意到 $3$ 张相同的「连续牌」在效果上完全等价于 $3$ 张「相同牌」。例如 $((1,2,3),(1,2,3),(1,2,3))$ 可以视作 $((1,1,1),(2,2,2),(3,3,3))$。 所以相同的「连续牌」的数量一定 $\le 2$。 考虑 DP。设 $f(i, a, b, c)$（$a,b,c \in [0,2]$）表示只考虑数值在 $1 \sim i$ 的牌，且有 $a$ 张 $(i-2,i-1,i)$，$b$ 张 $(i-1,i,i+1)$，$c$ 张 $(i, i+1, i+2)$。 这个状态里，因为我们只考虑数值在 $1 \sim i$ 的牌，所以 $b, c$ 并不算入这个状态的值里，只有 $a$ 算入。 显然对于第 $i$ 张牌而言，它自己能组成的「相同牌」的数量是 $\lfloor \frac{cnt_i-a-b-c}{3} \rfloor$。 综上转移为： $$ f(i,a,b,c) = \max_{d \in [0,2]}f(i-1,d,a,b)+a+\lfloor \frac{cnt_i-a-b-c}{3} \rfloor $$ 代码：<https://codeforces.com/contest/1110/submission/289999345>
正在渲染内容...
点赞
3
收藏
0
