Codeforces Round 612 (Div. 2) C. Garland——DP
内容提要
在Codeforces第612轮比赛中，C题目涉及动态规划。给定一个包含未知数（0）的序列，需要补全使得相邻数值的奇偶性相反的数量最少。通过定义DP数组并进行状态转移，最终输出最小的奇偶性相反数量。
延伸解读
贪心为何在此题失效
文章提到作者最初尝试贪心，但卡在第十二个样例。这说明局部最优选择无法保证全局相邻奇偶性相反次数最少，因为每个未知位置的填充会影响后续奇偶性匹配，存在后效性。动态规划通过记录已用奇数个数和当前位置奇偶性，能系统考虑所有可能，避免贪心短视。
DP状态设计的核心思路
代码定义dp[i][j][0/1]表示处理到第i+1个位置、共放置j个奇数、且该位置为偶/奇数时的最小相反次数。转移时根据当前位置是否已固定或为0，分别从上一位置奇偶性推导，若奇偶性变化则代价加1。这种设计将奇偶性序列的连续性约束转化为状态转移，清晰且易于实现。
实现中的关键细节
初始化时，若第一个位置为0，则dp[0][1][1]和dp[0][0][0]置0；若已给定数值，则根据其奇偶性设置对应状态。循环中j的上限取min(i+1, (n+1)/2)，确保奇数个数不超过总数一半。最终答案取dp[n-1][(n+1)/2][0]和[1]的较小值，保证恰好使用所有奇数。
Q&A
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则两个都需要填充。
最终输出的结果是什么？
最终输出的是最小的奇偶性相反数量。
