[数据结构与算法]【动态规划】酒鬼

题目描述

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

输入格式

第一行一个整数 N，表示有 N 个酒瓶。
接下有 N 行，第 i+1 行的数字代表酒瓶 i 中酒的体积（不必考虑单位）。

输出格式

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

样例输入

6
6
10
13
9
8
1

样例输出

33
问题提示
1≤N≤700，1≤体积≤10000

思路: 动态规划

1.状态与含义:

(1) 状态1: 最容易想到的状态就是 【当前所在酒瓶的序号i】但是如果只有 i 无法确定连续喝了多少瓶酒.(当然优化后不排除可以使用一维数组,但其解释性很差,不容易理解.)
(2) 状态2: 【当前已经连续喝酒的次数】,使用第二维来记录连续喝酒的次数
(3) 总结: dp[i][j]: 在第i瓶酒面前,且当前已经连续喝了j瓶酒时的最大喝酒量
例如:
dp[1][0]:在第1瓶酒前,且连续喝了0瓶酒,即第1瓶酒没有喝
dp[1][1]: 在第1瓶酒前,且连续喝了1瓶酒,即喝了第1瓶酒
dp[2][0]:在第2瓶酒前,且连续喝了0瓶酒,即没喝第2瓶酒,(但不确定第1瓶喝了没有,因为第2瓶不喝的话,连续喝酒数量重新归0)
dp[2][1]: 在第2瓶酒前,且连续喝了1瓶酒,即喝了第2瓶酒但没喝第1瓶酒
dp[2][2]:在第2瓶酒前,且连续喝了2瓶酒,即喝了第1,2瓶酒

2.赋予初值:

dp[1][0] = 0 : 不喝第1瓶
dp[1][1]＝ａ[1] : 喝第1瓶

3.状态转移方程:

dp[i][j]:表示处在第i瓶酒面前,且已经连续喝酒j次时的最大喝酒量
对于每瓶酒只有两大情况:

(1). 喝 :

喝的时候,又可以分成两种情况:
dp[i][1] : 喝,且当前为第1次连续喝,只可以来自于dp[i-1][0] 即i-1次没喝

即:dp[i][1] = dp[i-1][0]

dp[i][2] : 喝,且当前为第2次连续喝,由于当前已经喝了2次了,说明i-1必须喝了1次,即i-1也喝了

即:dp[i][2] = dp[i-1][1]

(2).不喝
dp[i][0]:不喝,连续次数为0即可
第i次不喝可以从三种情况而来:
dp[i-1][0]:第i-1次不喝,
dp[i-1][1]:第i-1次喝1次,
dp[i-1][2]:第i-1次连续喝2次,即第i-2次也喝了
取三种最大即可

即:dp[i][0] = max(dp[i-1][0],dp[i-1][1],dp[i-1][2])

代码

#include <bits/stdc++.h>
#define maxlen 10000
#define infinite 0x3f3f3f

using namespace std;

//1.dp[i][j]:面对第i瓶酒,连续喝j次时的最大能喝酒量
/**
 
2.状态转移方程:
	第i次喝:
		
		喝第1次: 
			dp[i][1] = dp[i-1][0]+a[i]
		喝第2次: 
			dp[i][2] = dp[i-1][1]+a[i]
	
	第i次不喝: 
		dp[i][0] = max(dp[i-1][0],dp[i-1][1],dp[i-1][2]) 
	
**/
int dp[maxlen][3]; 
int a[maxlen];
int n,maxn = -1;
int main() {
	
	cin>>n;
	for(int i = 1 ;i<=n ;i++){
		cin>>a[i];
	}
	
	//第1瓶酒不喝 
	dp[1][0] = 0;
	//第1瓶酒喝 
	dp[1][1] = a[1];
	//第1瓶酒时已经连续喝了2次,不存在这种情况 
	//dp[1][2] = -1; 
	
	for(int i = 2;i<=n ;i++){
		dp[i][0] = max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
		dp[i][1] = dp[i-1][0]+a[i];
		dp[i][2] = dp[i-1][1]+a[i];
		maxn = max(maxn,max(dp[i][0],max(dp[i][1],dp[i][2])));
	} 
	cout<<maxn<<endl;
   return 0;
}