首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7433

酒鬼 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 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>
这道题暂未补解析。