【不魔怔】菜就多练。

__Allen_123__ · 2024-10-12 23:19:28 · 题解

你正在备战一场想象学竞赛。

你有 n 块完整的空闲时间，长度为 b_i。初始时，每个时间都被提前安排了其用途 a_i，用 1,2,3 来表示：

1. 学习想象学竞赛知识点；
2. 参加想象学模拟竞赛；
3. 通过 Grosphi 这款应用锻炼自己的想象能力。

你想知道，在这些完整的空闲时间不被拆开的情况下，能否改变一些时间原有的用途，使学习知识点、参加模拟赛、打开 Grosphi 的时间相同。如果可以做到，最少需要改变多少块时间的用途。

你马上想到，如果所有时间之和（记为 sum）不能被 3 整除，那么只能让做每件事情的总时间为小数，显然不能做到。如果可以被 3 整除，那做每件事情的时间就分别为 \frac{sum}{3}。

你考虑进行 dp。设 dp_{i,j,k} 代表考虑了前 i 段时间，分配给学习知识点、打模拟赛的时间分别为 j,k，则分配给 Grosphi 的时间显然可求。

考虑到第 i 片时间时，你会枚举它分别用作三个用途对应的 dp 值。根据题意，你想到：

• 当用途为 1 时，dp_{i,j,k}=dp_{i-1,j-b_i,k}+[a_i\ne 1](j\ge b_i)；
• 当用途为 2 时，dp_{i,j,k}=dp_{i-1,j,k-b_i}+[a_i\ne 2](j\ge b_i)；
• 当用途为 3 时，dp_{i,j,k}=dp_{i-1,j,k}+[a_i\ne 3](sum-i-j\ge b_i)。

根据题意，你进行了 dp，并合理地安排了自己的时间。你的 AC 代码。

合理地安排了时间……是吗？

面对着自己不堪入目的成绩，你再次陷入了沉思。你对自己的时间安排十分满意，但这一切似乎只是表象。使三者的时间都相等，不尽科学，甚至有一部分时间还被用来浪费。纵观这一切，你水平之低源自于你的不合理的安排，才导致了如今的结果。你想回到过去重新来过，但一切已为时已晚。走到死胡同的尽头，你才顿悟：学习和练习才能充分提升自己的想象学竞赛水平。

所以，菜就多练。