Shiroha白羽的博客
·
Codeforces Round 612 (Div. 2) C. Garland——DP
💡
原文中文，约2300字，阅读约需6分钟。
📝
内容提要
在Codeforces第612轮比赛中，C题目涉及动态规划。给定一个包含未知数（0）的序列，需要补全使得相邻数值的奇偶性相反的数量最少。通过定义DP数组并进行状态转移，最终输出最小的奇偶性相反数量。
🎯
关键要点
- 在Codeforces第612轮比赛中，C题目涉及动态规划。
- 给定一个包含未知数（0）的序列，需要补全使得相邻数值的奇偶性相反的数量最少。
- 相邻数值的奇偶性相反：两个相邻的数值，其中一个为奇数，另一个为偶数。
- 使用动态规划定义DP数组，状态转移方程为：dp[i][j][1]和dp[i][j][0]。
- 根据位置的数值是否为0，决定需要填充的奇数或偶数。
- 最终输出最小的奇偶性相反数量。
❓
延伸问答
Codeforces第612轮比赛的C题目主要涉及什么内容？
C题目主要涉及动态规划，要求补全一个包含未知数的序列，使得相邻数值的奇偶性相反的数量最少。
如何定义动态规划的DP数组？
DP数组定义为dp[i][j][0/1]，表示第i+1个位置放了偶数或奇数，且到第i+1处总共放了j个奇数。
相邻数值的奇偶性相反是什么意思？
相邻数值的奇偶性相反是指两个相邻的数值中，一个为奇数，另一个为偶数。
状态转移方程是如何构建的？
状态转移方程为：dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, dp[i - 1][j - 1][1])，dp[i][j][0] = min(dp[i - 1][j][1] + 1, dp[i - 1][j][0])。
如何处理序列中的未知数（0）？
根据位置的数值是否为0，决定需要填充的奇数或偶数，如果为0则两个都需要填充。
最终输出的结果是什么？
最终输出的是最小的奇偶性相反数量。
🏷️
标签
➡️
