T1. 酒鬼

Santo 刚刚与房东打赌赢得了一间在 New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令 Santo 高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续喝三瓶，不然会给你带来坏运气。”

现在可怜的 Santo 站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。

时间限制：2 s
内存限制：128 MB

• 输入
  第一行一个整数 $N$，有 $N$ 个酒瓶。$N\le 700$。
  接下有 $N$ 行，第 $i+1$ 行的数字代表酒瓶 $i$ 中酒的体积。
• 输出
  一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。数据保证答案在 $32$ 位整数范围内。
• 样例输入

  6
  6
  10
  13
  9
  8
  1
  

• 样例输出

  33
  

思路分析

此题考查动态规划，属于基础题。

定义 $f_{i,0}$ 表示第 $i$ 瓶酒没有喝的情况下可以喝到的酒的最大体积，$f_{i,1}$ 表示第 $i$ 瓶酒喝了的情况下可以喝到的酒的最大体积。

• 若第 $i$ 瓶酒没有喝，则可以考虑第 $i-1$ 瓶酒喝与不喝；
• 若第 $i$ 瓶酒喝了，则考虑第 $i-1$ 瓶酒没有喝，以及第 $i-2$ 瓶酒没有喝但第 $i-1$ 瓶酒喝了的情况。

不难得出状态转移方程为
f i , 0 = max ⁡ { f i − 1 , 0 , f i − 1 , 1 } f i , 1 = max ⁡ { f i − 1 , 0 , f i − 2 , 0 + a i − 1 } + a i f_{i,0} = \max\{f_{i-1,0}, f_{i-1,1}\} \\ f_{i,1} = \max\{f_{i-1,0}, f_{i-2,0} + a_{i-1}\} + a_i fi,0​=max{fi−1,0​,fi−1,1​}fi,1​=