题目解析
动态规划；状态DP
考虑进行状态DP，并从前到后考虑所有礼盒，那么会涉及到 666 种状态。
1. 未使用魔法，礼盒中的糖果数量状态为 AAA。
2. 使用 111 次魔法，礼盒中的糖果状态为 BBB。
3. 使用 111 次魔法，礼盒中的糖果状态为 AAA（即第一次使用魔法的区间结束了）。
4. 使用 222 次魔法，礼盒中的糖果状态为 CCC。（即和第一次使用魔法的区间重合的部分）
5. 使用 222 次魔法，礼盒中的糖果状态为 BBB。（即第和第一次使用魔法的区间不重合的部分）
6. 使用 222 次魔法，礼盒中的糖果状态为 AAA。（即两次使用魔法的区间全部结束）
令 dp0,dp1,⋯ ,dp5dp_0, dp_1, \cdots, dp_5dp0 ,dp1 ,⋯,dp5 分别对应以上 666 种状态下前 iii 个礼盒能够拿到的最多的糖果的数量；那么有以下关系转移方式。
令 dpIdpIdpI 为前 iii 个礼盒能够拿到的最多的糖果的数量，讨论如何从前 i−1i - 1i−1 个礼盒能够拿到的最多的糖果数量 dpdpdp 转移到 dpIdpIdpI。
1. dpI0=dp0+aidpI_0 = dp_0 + a_idpI0 =dp0 +ai
2. dpI1=max(dp0,dp1)+bidpI_1 = \max{(dp_0, dp_1)} + b_idpI1 =max(dp0 ,dp1 )+bi
3. dpI2=max(dp1,dp2)+aidpI_2 = \max{(dp_1, dp_2)} + a_idpI2 =max(dp1 ,dp2 )+ai
4. dpI3=max(dp0,dp1,dp3)+cidpI_3 = \max{(dp_0, dp_1, dp_3)} + c_idpI3 =max(dp0 ,dp1 ,dp3 )+ci
5. dpI4=max(dp2,dp3,dp4)+bidpI_4 = \max{(dp_2, dp_3, dp_4)} + b_idpI4 =max(dp2 ,dp3 ,dp4 )+bi
6. dpI5=max(dp3,dp4,dp5)+aidpI_5 = \max{(dp_3, dp_4, dp_5)} + a_idpI5 =max(dp3 ,dp4 ,dp5 )+ai
最终 max(dp0,dp1,⋯ ,dp5)\max{(dp_0, dp_1, \cdots, dp_5)}max(dp0 ,dp1 ,⋯,dp5 ) 便是答案。
时间复杂度 O(N)\mathrm{O}(N)O(N)。
AC代码
