口罩装箱问题

题目描述:

疫情防控期间,某工厂为了将流水线上已生产的口罩及时装箱，并尽量分配给更多的疫情地区，需要设计一个程序实现自动化装箱。

装箱要求为：流水线上生产的每包口罩数量有可能不同，装入箱子的口罩必须为流水线上连续的若干包，每箱内的口罩数量必须相同，在已知每包口罩数量和口罩总包数的前提下，装尽可能多的箱子。

例1：某流水线上有8包口罩,每包口罩的数量和装箱安排如下表：

序号	1	2	3	4	5	6	7	8
数量	12	3	9	6	6	9	3	12
箱号(方案1)	1	2	2	3	3	4	4	5
箱号(方案2)	1	1	2	2	3	3	4	4
箱号(方案3)	1	1	1	1	2	2	2	2

在上述情况下，有3种分箱方案,方案1为最优方案。

例2：某流水线上有8包口罩,每包口罩的数量和装箱安排如下表：

序号	1	2	3	4	5	6	7	8
数量	1	3	5	7	9	11	13	15

在上述情况下，没有符合要求的装箱方案。

输入格式:

一个整数n，表示有n包口罩。

接下来n个整数，表示每包口罩的数量。

输出格式:

一个整数，表示最多能装箱的数量。

如果没装箱方案，则输出“No Answer!”

样例输入:

8
12 3 9 6 6 9 3 12

样例输出:

5

提示:

1<=n<=5000

^{每包口罩的数量不超过1000个，要注意一包中口罩的数量有可能为0。}

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创