会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
设灯带下标从 1 到 n，第 i 位为 0 表示熄灭、为 1 表示点亮。目标是把至多 k 个 0 改成 1 后，最大化所有极大连续 1 段长度平方之和。
用动态规划。令 dp[i][g] 表示只考虑前 i 个位置、恰好把 g 个 0 改成 1 时的最大积分。转移时枚举最后一段连续点亮是否以位置 i 结尾：
- 若以 i 结尾：枚举该段左端点 j，把 [j,i] 中所有
0 都点亮，设其中 0 的个数为 z。若 z≤g，则可从 dp[j−1][g−z] 转移，并加上该段贡献 (i−j+1)2。
- 若不以 i 结尾：直接继承 dp[i−1][g]。
