A49997. 酒鬼
填空题
较难
知识点
题目描述
酒鬼
题目描述
Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，并且不能连续超过三瓶，不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。
输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行，第I+1行的数字代表酒瓶I中酒的体积。
输出
一个数字，喝的酒的最大总体积。遵守以上规则，使得三个连续瓶子中至少一个瓶子是满的。
样例输入
6
6
10
13
9
8
1
样例输出
33
参考答案
#include<bits/stdc++.h>
using namespace std;
int n;
int a[701];
int f[701];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=a[1];
f[2]=a[1]+a[2];
f[3]=max(max(a[1]+a[2],a[1]+a[3]),a[1]+a[3]);
for(int i=4;i<=n;i++)
{
f[i]=f[i-1];
f[i]=max(f[i],max(f[i-2],f[i-3]+a[i-1])+a[i]);
}
cout<<f[n]<<endl;
return 0;
}答案解析
这道题我列出思路，然后写代码一次就成了，一点错都没有，突然感觉自己应该是有点门道了，做了这么多动态规划的题终于有点小成就感了，虽然这题还挺简单的哈哈
首先这题是一个背包问题~
1、首先就是考虑第i瓶酒到底喝还是不喝的问题，
（1）不喝就好办了，f[i]=f[i-1]
（2）喝的话就得考虑一下具体怎么喝法了，因为不能连续喝三瓶，所以，就是i和i-1，i-2不能同时都喝:
不喝i-1的情况：f[i-2]+a[i]；
不喝i-2的情况：f[i-3]+a[i-1]+a[i];
2、最后取三种情况的最大值就好啦！
上一题
下一题