1 条题解

  • 0
    @ 2025-4-4 14:01:24
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int pizzaAmount;
    vector<int> pizzaPieces;
    //三维数组,result[left][right][0]表示吃货能吃到的最大数,result[left][right][1]表示馋嘴能吃到的最大数
    vector<vector<vector<unsigned long>>> result;
    
    //披萨是一个圆,通过这个函数让数组首尾相接
    int legalIndex(int input) {
    	if (input < 0)
    		return pizzaAmount - 1;
    	else if (input >= pizzaAmount)
    		return 0;
    	return input;
    }
    
    //返回从left到right,某人能吃到的最大的披萨,turn=0表示吃货,turn=1表示馋嘴
    unsigned long getMax(int left, int right, int turn)
    {
    	if (left == right)
    	{
    		//最后一块饼,因为pizza数为奇数,吃货先吃,所以他必定比馋嘴多吃一个也就是最后这一个
    		if (turn == 0)
    			return pizzaPieces[left];
    		else
    			return 0;
    	}
    	//如果已有结果则直接返回
    	if (result[left][right][turn] > 0)
    		return result[left][right][turn];
    	//吃货的回合,选择两种情况下(吃左边/吃右边)最大的
    	if (turn == 0)
    	{
    		unsigned long eatLeft = getMax(legalIndex(left - 1), legalIndex(right), 1) + pizzaPieces[left];
    		unsigned long eatRight = getMax(legalIndex(left), legalIndex(right + 1), 1) + pizzaPieces[right];
    		result[left][right][0] = max(eatLeft, eatRight);
    
    	}
    	//馋嘴的回合,在左和右两个选择中固定选最大的
    	else
    	{
    		if (pizzaPieces[left] > pizzaPieces[right])
    			result[left][right][1] = getMax(legalIndex(left - 1), right, 0);
    		else
    			result[left][right][1] = getMax(left, legalIndex(right + 1), 0);
    
    	}
    	return result[left][right][turn];
    }
    
    int main(int argc, char *argv[])
    {
    	cin >> pizzaAmount;
    	for (int i = 0; i < pizzaAmount; i++)
    	{
    		int temp;
    		cin >> temp;
    		pizzaPieces.push_back(temp);
    	}
    	//初始化三维数组
    	result = vector<vector<vector<unsigned long>>>(pizzaAmount, vector<vector<unsigned long>>(pizzaAmount, vector<unsigned long>(2, 0)));
    
    	unsigned long max = 0;
    	for (int i = 0; i < pizzaAmount; i++)
    	{
    		//一开始从吃货开始吃
    		unsigned long get = getMax(legalIndex(i - 1), legalIndex(i + 1),1)+pizzaPieces[i];
    		if (get > max)
    			max = get;
    	}
    	cout << max << endl;
    	
    	return 0;
    }
    
    • 1

    信息

    ID
    110
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    (无)
    递交数
    186
    已通过
    65
    上传者