简答题
偏难
#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 <bits/stdc++.h>
using namespace std;
int f[701][5];
int main() {
int n;
int a[1000];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
f[i][0] = f[i - 1][3];
int mx = f[i][0];
for (int j = 1; j <= 2; j++) {
f[i][j] = f[i - 1][j - 1] + a[i];
mx = max(mx, f[i][j]);
}
f[i][3] = mx;
}
cout << f[n][3];
return 0;
}</pre><pre class="brush:cpp;toolbar:false">// 参考答案2 递推
#include <bits/stdc++.h>
using namespace std;
int n, a[10005], dp[10005][2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dp[1][0] = 0; // 第一瓶没喝
dp[1][1] = a[1]; // 第一瓶喝了
for (int i = 2; i <= 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 << max(dp[n][0], dp[n][1]);
return 0;
}</pre>
这道题暂未补解析。