题目描述
圆桌边放了一圈红包形成一个环形，每个红包的金额不同，围绕圆桌走一圈选择若干红包，规则是不能拿相邻的红包，请问能拿到红包最多的总金额是多少？（红包金额保存在一个数组中，认为数组第一个元素和最后一个元素相邻，形成闭环）
输入包括多行：
第一行为整数N，0<N<20；
以下N行，每行为一个数组，每个元素为一个红包的金额，数值为0或100以内的整数，以逗号隔开，如是空行表明没有红包如：
2
1,2
1,3,4
输出包括N行，每行一个数字，为拿到红包的总金额，如：
2
4
思路：
2 4 5 1 2 8 9 4 3 vec
2 4 7 7 9 15 18 19 21 v
1 0 1 1 1 1 1 1 1 m
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int coutMoney(vector<int> vec){
int len=vec.size();
vector<int> v(len,0); //记录最大值
vector<int> m(len,0); //记录有没有用到第一个红包
if(len<=3){ //元素少于3个做特殊讨论
return *max_element(vec.begin(),vec.end());
}else{
v[0]=vec[0];
m[0]=1;
v[1]=vec[1];
m[1]=0;
for(int i=2;i<len;i++){
if(v[i-2]+vec[i]>v[i-1]){
v[i]=v[i-2]+vec[i];
m[i]=m[i-2];
}else{
v[i]=v[i-1];
m[i]=m[i-1];
}
}
}
if(m[len-1]==1)
return v[len-2];
else
return v[len-1];
}
int main(){
//const int n=9;
//int a[n]={2,4,5,1,2,8,9,4,3};
//const int n=3;
//int a[n]={2,4,5};
const int n=6;
int a[n]={2,3,4,1,2,4};
vector<int> vec(a,a+n);
cout<<coutMoney(vec)<<endl;
system("pause");
}