核心思路

1. 关键变量定义

设 $S = \sum_{i=1}^n a_i$（整个序列中 1 的个数）。

根据定义： [ b_1 = 0 - S = -S ] [ b_{n+1} = S - 0 = S ] 所以： [ b_1 = -S,\quad b_{n+1} = S ]

误差限制： [ |b_1 - c_1| + |b_{n+1} - c_{n+1}| = |-S - c_1| + |S - c_{n+1}| \leq k ] 这给出了 $S$ 的可能范围。

2. 递推关系

设 $p_i = \sum_{j=1}^{i-1} a_j$（前 $i-1$ 项中 1 的个数），则： [ b_i = p_i - (S - p_i) = 2p_i - S ] 所以： [ p_i = \frac{b_i + S}{2} ]

由于 $p_i$ 必须是整数且 $0 \leq p_i \leq S$，$p_{i+1} - p_i \in \{0,1\}$。

3. 动态规划解法

代码使用滚动数组 DP，状态为：

• stk[u][j]：存储可能的 $x$ 值（偏移后的状态）
• val[u][j]：存储对应的累计误差
• pre[i][x]：记录前驱选择（0 或 1）

状态转移： 设当前状态 $x = 2p_i - S - c_i + m$（加 $m$ 是为了保证非负）， 选择 $a_i = 0$ 或 $1$ 时：

• 若 $a_i = 0$，则 $p_{i+1} = p_i$，$b_{i+1} = 2p_i - S$
• 若 $a_i = 1$，则 $p_{i+1} = p_i + 1$，$b_{i+1} = 2p_i + 2 - S$

误差更新： [ \text{new_error} = \text{old_error} + |b_{i+1} - c_{i+1}| ] 若累计误差超过 $k$ 则剪枝。

4. 算法流程

1. 枚举 S：从 0 到 n 枚举可能的 1 的个数
2. 可行性检查：
   • 首先检查 $| -S - c_1 | + | S - c_{n+1} | \leq k$
3. DP 过程：
   • 初始化：$p_1 = 0$，对应状态 $x = -S - c_1 + m$
   • 递推：对于每个 $i$，尝试 $a_i = 0$ 或 $1$，更新状态和误差
   • 剪枝：误差超过 $k$ 的状态被丢弃
4. 构造解：
   • 如果找到可行解，从后往前根据 pre 数组恢复 $a_i$

重要公式

1. 首尾约束： [ | -S - c_1 | + | S - c_{n+1} | \leq k ]

2. b_i 与 p_i 关系： [ b_i = 2p_i - S ]

3. 状态表示： [ x = 2p_i - S - c_i + m ] （$m$ 是偏移量，确保下标非负）

4. 误差计算： [ \text{error} = \sum_{i=1}^{n+1} |2p_i - S - c_i| ]

复杂度分析

• 枚举 $S$：$O(n)$
• 每个 $S$ 的 DP：状态数受 $k$ 限制，为 $O(n \cdot k)$
• 总复杂度：$O(n^2 \cdot k)$ 最坏，但实际剪枝很有效