3N pizza slice.cpp

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int solve(int index,int endindex,vector<int> &slice,int n){
	if(n==0 || index>endindex){
		return 0;
	}
	int take=slice[index]+solve(index+2,endindex,slice,n-1);
	int nottake=0+ solve(index+1,endindex,slice,n);
	return max(take,nottake);
}
int solvemem(int index,int endindex,vector<int> &slice,int n,vector<vector<int> > &dp){
	if(n==0 || index>endindex){
		return 0;
	}
	if(dp[index][n]!=-1){
		return dp[index][n];
	}
	int take=slice[index]+solvemem(index+2,endindex,slice,n-1,dp);
	int nottake=0+ solvemem(index+1,endindex,slice,n,dp);
	return dp[index][n]=max(take,nottake);
}
int maxslice(vector<int> &slice){
//	int k=slice.size();
//	int case1=solve(0,k-2,slice,k/3);
//	int case2=solve(1,k-1,slice,k/3);
//	return max(case1,case2);
	int k=slice.size();
	vector<vector<int> > dp1(k,vector<int> (k,-1));
	vector<vector<int> > dp2(k,vector<int> (k,-1));
	int case1=solvemem(0,k-2,slice,k/3,dp1);
	int case2=solvemem(1,k-1,slice,k/3,dp2);
	return max(case1,case2);
}

int main(){
    vector<int> slice;
    slice.push_back(1);
	slice.push_back(2);
	slice.push_back(3);
	slice.push_back(4);
	slice.push_back(5);
	slice.push_back(6);
	int ans=maxslice(slice);
	cout<<ans<<endl;
}