牛客周赛 Round 15 解题报告 简介

详细的解题报告

https://blog.nowcoder.net/n/331464bebcdb4fe29af232c84b1c2919

---

A. 枚举签到题, 只要枚举前后两段的分界点,然后判定末尾的奇偶是否一致

B. 枚举最终的字母,然后评估代价,这边单字母的转移代价

> cost = min(abs(i - j), 26 - abs(i - j))

这符合环状结构

C. 有3种解法

  1. 3维DP,正向递推,从而求解最终的结果
  2. 脑筋急转弯,分类讨论字符串长度
  3. n = 1,任意字符即可
  4. n = 2,前后两字符不相等就行
  5. n = 3,只有 101, 121, 202, 020这几个字符串满足需求
  6. n = 4,只有0,2交替更迭的字符串才满足需求
  7. dfs 构造

dfs的深度有1000, 但是它分支少且短,而且找到任意解,立刻返回

D. 树形DP

这题和打家劫舍树形DP版的区别在于, 它本质上不是点不相邻,而是边不相邻

如果能提取到这个关键信息,就容易解决了。

全部评论

相关推荐

4 1 评论
分享
牛客网
牛客企业服务