简答题 偏难
#7123

酒鬼 Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体…

酒鬼

Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是,瓶子中的酒都有不同的味道。房东说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续超过三瓶,不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。

时间限制:2000

内存限制:131072

输入

第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。

输出

一个数字,喝的酒的最大总体积。遵守以上规则,使得三个连续瓶子中至少一个瓶子是满的。

样例输入

6
6
10
13
9
8
1

样例输出

33
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int f[701][5]; int main() {   int n;   int a[1000];   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     cin &gt;&gt; a[i];   }   for (int i = 1; i &lt;= n; i++) {     f[i][0] = f[i - 1][3];     int mx = f[i][0];     for (int j = 1; j &lt;= 2; j++) {       f[i][j] = f[i - 1][j - 1] + a[i];       mx = max(mx, f[i][j]);     }     f[i][3] = mx;   }   cout &lt;&lt; f[n][3];   return 0; }</pre><pre class="brush:cpp;toolbar:false">// 参考答案2  递推 #include &lt;bits/stdc++.h&gt; using namespace std; int n, a[10005], dp[10005][2]; int main() {   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++)     cin &gt;&gt; a[i];   dp[1][0] = 0;    // 第一瓶没喝   dp[1][1] = a[1]; // 第一瓶喝了   for (int i = 2; i &lt;= n; i++) {     // 第i瓶没喝=max(i-1瓶没喝,i-1瓶喝了)     dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);     // 第i瓶喝了=max(i-1瓶没喝,i-2瓶没喝+i-1瓶喝了)     dp[i][1] = a[i] + max(dp[i - 1][0], dp[i - 2][0] + a[i - 1]);   }   cout &lt;&lt; max(dp[n][0], dp[n][1]);   return 0; }</pre>
这道题暂未补解析。