酒鬼 Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天，他来到这个大客厅

酒鬼
Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是，瓶子中的酒都有不同的味道。房东说道："你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。"现在可怜的Santo站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。
时间限制：2000
内存限制：131072
输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行，第I+1行的数字代表酒瓶I中酒的体积。
输出
一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。
样例输入

样例输出

解析：

【喵呜刷题小喵解析】：本题是一道动态规划问题，可以使用动态规划算法来解决。首先，我们定义一个数组dp，其中dp[i]表示前i个瓶子中喝的酒的最大总体积。然后，我们遍历每个瓶子，对于每个瓶子i，我们尝试从i-2到i+1中选择连续的瓶子，使得选择的瓶子中至少有一个瓶子是满的，并且喝的酒的总体积最大。具体来说，我们遍历i-2到i+1中的每个瓶子j，如果j在有效范围内，则计算dp[j] + volume[i-1]的值，其中volume[i-1]表示第i个瓶子中酒的体积。然后，我们更新max_volume为dp[j] + volume[i-1]和max_volume的较大值。最后，我们将max_volume的值赋给dp[i]，表示前i个瓶子中喝的酒的最大总体积。最终，我们输出dp[N]的值，即前N个瓶子中喝的酒的最大总体积。需要注意的是，由于题目中要求不能连续超过三瓶，因此我们在遍历瓶子时，只需要遍历i-2到i+1中的瓶子即可。另外，由于题目中要求遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的，因此在选择连续的瓶子时，需要保证至少有一个瓶子是满的。在本题的示例中，酒瓶的编号为1到6，其中第1个瓶子的体积为6，第2个瓶子的体积为10，第3个瓶子的体积为13，第4个瓶子的体积为9，第5个瓶子的体积为8，第6个瓶子的体积为1。根据动态规划算法，我们可以计算出喝的酒的最大总体积为33。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！