思路：动态规划

问题

• 披萨切片：披萨被切成 N（奇数）个大小各不相同的切片。
• 分配规则：
  • 第一步：“吃货”可以任意选择一个切片。
  • 之后：两人轮流从当前剩余披萨的两端（左端或右端）选择切片。
  • “馋嘴”策略：每次总是选择当前两端中较大的切片。
• 目标：计算“吃货”能够获得的最大披萨总大小。

解决思路

1. 线性化披萨切片：由于披萨是圆形的，我们需要考虑所有可能的起始点。对于每一个起始点，将披萨切片线性化，便于应用动态规划。

2. 动态规划表 DP[l][r]：

   • 定义 DP[l][r] 表示在当前区间 [l, r] 中，“吃货”能够获得的最大披萨总大小。
   • 选择策略：
     • 选择左端 l：
       • “吃货”选择切片 l，然后“馋嘴”选择 l+1 或 r 中较大的一个。
       • 根据“馋嘴”的选择，更新区间为 [l+2, r] 或 [l+1, r-1]。
     • 选择右端 r：
       • “吃货”选择切片 r，然后“馋嘴”选择 l 或 r-1 中较大的一个。
       • 根据“馋嘴”的选择，更新区间为 [l+1, r-1] 或 [l, r-2]。
   • DP[l][r] 的值为“吃货”选择左端或右端后的最大值。

3. 遍历所有起始点：对于每一个可能的起始点，计算“吃货”在该起始点下能够获得的最大披萨总大小，最终取所有起始点中的最大值。

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    
    int N;
    cin >> N; // 读取披萨切片的数量
    vector<ll> slices(N);
    for(int i=0;i<N;i++) cin >> slices[i]; // 读取每个切片的大小
    
    // 为了处理圆形披萨，将切片数组复制一遍
    vector<ll> double_slices(2*N);
    for(int i=0;i<2*N;i++) double_slices[i] = slices[i%N];
    
    // 初始化 DP 表，DP[l][r] 表示在当前区间 [l, r] 中，“吃货”能获得的最大披萨总大小
    vector<vector<ll>> DP(N, vector<ll>(N, 0));
    
    ll max_total = 0; // 记录“吃货”能获得的最大总大小
    
    // 遍历所有可能的起始切片
    for(int start=0; start<N; start++){
        // 对于当前起始点，线性化披萨切片（无需创建新数组，直接通过 double_slices 访问）
        
        // 填充 DP 表中区间长度为 1 的情况
        for(int i=0; i<N; i++) {
            DP[i][i] = double_slices[start + i];
        }
        
        // 填充区间长度从 2 到 N 的 DP 表
        for(int length=2; length<=N; length++){
            for(int l=0; l + length <= N; l++){
                int r = l + length -1; // 当前区间的右端点
                
                // “吃货”选择左端切片 l
                ll take_left = double_slices[start + l];
                ll next_total_l;
                // “馋嘴”选择 l+1 或 r 中较大的切片
                if(double_slices[start + l +1] >= double_slices[start + r]){
                    // “馋嘴”选择 l+1，新的区间为 [l+2, r]
                    if(l+2 > r){
                        next_total_l = 0; // 区间无效，无法继续选择
                    }
                    else{
                        next_total_l = DP[l+2][r];
                    }
                }
                else{
                    // “馋嘴”选择 r，新的区间为 [l+1, r-1]
                    if(l+1 > r-1){
                        next_total_l = 0; // 区间无效，无法继续选择
                    }
                    else{
                        next_total_l = DP[l+1][r-1];
                    }
                }
                ll total_l = take_left + next_total_l; // “吃货”选择左端后的总和
                
                // “吃货”选择右端切片 r
                ll take_right = double_slices[start + r];
                ll next_total_r;
                // “馋嘴”选择 l 或 r-1 中较大的切片
                if(double_slices[start + l] >= double_slices[start + r -1]){
                    // “馋嘴”选择 l，新的区间为 [l+1, r-1]
                    if(l+1 > r-1){
                        next_total_r = 0; // 区间无效，无法继续选择
                    }
                    else{
                        next_total_r = DP[l+1][r-1];
                    }
                }
                else{
                    // “馋嘴”选择 r-1，新的区间为 [l, r-2]
                    if(l > r-2){
                        next_total_r = 0; // 区间无效，无法继续选择
                    }
                    else{
                        next_total_r = DP[l][r-2];
                    }
                }
                ll total_r = take_right + next_total_r; // “吃货”选择右端后的总和
                
                // 选择“吃货”选择左端或右端后较大的总和
                DP[l][r] = max(total_l, total_r);
            }
        }
        
        // 更新“吃货”在所有起始点中的最大总和
        max_total = max(max_total, DP[0][N-1]);
    }
    
    cout << max_total; // 输出“吃货”能获得的最大披萨总大小
}

python

import sys
import sys
import sys
import sys

def main():
    import sys
    import sys
    sys.setrecursionlimit(1 << 25)
    
    # 读取所有输入
    N = int(input())  # 读取披萨切片的数量
    slices = []  # 读取每个切片的大小
    for i in range(N):
        slices.append(int(input()))
    
    max_total = 0  # 记录“吃货”能获得的最大总大小
    
    # 遍历所有可能的起始切片
    for start in range(N):
        # 线性化披萨切片，从当前起始点开始
        linear = slices[start:] + slices[:start]
        
        # 初始化 DP 表，DP[l][r] 表示在当前区间 [l, r] 中，“吃货”能获得的最大披萨总大小
        DP = [[0]*N for _ in range(N)]
        
        # 填充区间长度为 1 的情况
        for i in range(N):
            DP[i][i] = linear[i]
        
        # 填充区间长度从 2 到 N 的 DP 表
        for length in range(2, N+1):
            for l in range(N - length +1):
                r = l + length -1  # 当前区间的右端点
                
                # “吃货”选择左端切片 l
                take_left = linear[l]
                if linear[l+1] >= linear[r]:
                    # “馋嘴”选择 l+1，新的区间为 [l+2, r]
                    if l + 2 > r:
                        next_total_l = 0  # 区间无效，无法继续选择
                    else:
                        next_total_l = DP[l+2][r]
                else:
                    # “馋嘴”选择 r，新的区间为 [l+1, r-1]
                    if l +1 > r -1:
                        next_total_l = 0  # 区间无效，无法继续选择
                    else:
                        next_total_l = DP[l+1][r-1]
                total_l = take_left + next_total_l  # “吃货”选择左端后的总和
                
                # “吃货”选择右端切片 r
                take_right = linear[r]
                if linear[l] >= linear[r-1]:
                    # “馋嘴”选择 l，新的区间为 [l+1, r-1]
                    if l +1 > r -1:
                        next_total_r = 0  # 区间无效，无法继续选择
                    else:
                        next_total_r = DP[l+1][r-1]
                else:
                    # “馋嘴”选择 r-1，新的区间为 [l, r-2]
                    if l > r -2:
                        next_total_r = 0  # 区间无效，无法继续选择
                    else:
                        next_total_r = DP[l][r-2]
                total_r = take_right + next_total_r  # “吃货”选择右端后的总和
                
                # 选择“吃货”选择左端或右端后较大的总和
                DP[l][r] = max(total_l, total_r)
        
        # 更新“吃货”在所有起始点中的最大总和
        if DP[0][N-1] > max_total:
            max_total = DP[0][N-1]
    
    print(max_total)  # 输出“吃货”能获得的最大披萨总大小

if __name__ == "__main__":
    main()

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 读取输入，提升读取效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 读取披萨切片的数量 N
        int N = Integer.parseInt(br.readLine().trim());
        
        // 读取接下来的 N 行，每行一个整数，表示每个切片的大小
        long[] slices = new long[N];
        for(int i = 0; i < N; i++) {
            slices[i] = Long.parseLong(br.readLine().trim());
        }
        
        long maxTotal = 0; // 记录“吃货”能获得的最大总大小
        
        // 遍历所有可能的起始切片
        for(int start = 0; start < N; start++) {
            // 线性化披萨切片，从当前起始点开始
            long[] linear = new long[N];
            for(int i = 0; i < N; i++) {
                linear[i] = slices[(start + i) % N];
            }
            
            // 初始化 DP 表，DP[l][r] 表示在当前区间 [l, r] 中，“吃货”能获得的最大披萨总大小
            long[][] DP = new long[N][N];
            
            // 填充区间长度为 1 的情况，即只有一个切片时，“吃货”只能选择这一片
            for(int i = 0; i < N; i++) {
                DP[i][i] = linear[i];
            }
            
            // 填充区间长度从 2 到 N 的 DP 表
            for(int length = 2; length <= N; length++) {
                for(int l = 0; l + length <= N; l++) {
                    int r = l + length - 1; // 当前区间的右端点
                    
                    // “吃货”选择左端切片 l
                    long takeLeft = linear[l];
                    long nextTotalL;
                    // “馋嘴”选择剩下的切片中的较大者
                    if(linear[l + 1] >= linear[r]) {
                        // “馋嘴”选择 l+1，新的区间为 [l+2, r]
                        if(l + 2 > r) {
                            nextTotalL = 0; // 区间无效，无法继续选择
                        }
                        else {
                            nextTotalL = DP[l + 2][r];
                        }
                    }
                    else {
                        // “馋嘴”选择 r，新的区间为 [l+1, r-1]
                        if(l + 1 > r - 1) {
                            nextTotalL = 0; // 区间无效，无法继续选择
                        }
                        else {
                            nextTotalL = DP[l + 1][r - 1];
                        }
                    }
                    long totalL = takeLeft + nextTotalL; // “吃货”选择左端后的总和
                    
                    // “吃货”选择右端切片 r
                    long takeRight = linear[r];
                    long nextTotalR;
                    // “馋嘴”选择剩下的切片中的较大者
                    if(linear[l] >= linear[r - 1]) {
                        // “馋嘴”选择 l，新的区间为 [l+1, r-1]
                        if(l + 1 > r - 1) {
                            nextTotalR = 0; // 区间无效，无法继续选择
                        }
                        else {
                            nextTotalR = DP[l + 1][r - 1];
                        }
                    }
                    else {
                        // “馋嘴”选择 r-1，新的区间为 [l, r-2]
                        if(l > r - 2) {
                            nextTotalR = 0; // 区间无效，无法继续选择
                        }
                        else {
                            nextTotalR = DP[l][r - 2];
                        }
                    }
                    long totalR = takeRight + nextTotalR; // “吃货”选择右端后的总和
                    
                    // 选择“吃货”选择左端或右端后较大的总和
                    DP[l][r] = Math.max(totalL, totalR);
                }
            }
            
            // 更新“吃货”在所有起始点中的最大总和
            if(DP[0][N - 1] > maxTotal) {
                maxTotal = DP[0][N - 1];
            }
        }
        
        // 输出“吃货”能获得的最大披萨总大小
        System.out.println(maxTotal);
    }
}

题目描述

“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数拿形小块。但是粗心服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。 由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法:从“吃货”开始，轮流取披萨。除了第-块披萨可以任意选取以外，其他都必须从缺口开始选。 他俩选披萨的思路不同。“馋嘴”每次都会选最大块的拨萨，而且“吃货”知道“馋嘴”的想法。 已知披萨小块的数量以及每块的大小，求“吃货”能分得的最大的披萨大小的总和。

输入描述

第1行为一个正整数奇数 $N$ ，表示披萨小块数量。其中 $3 \le N < 500$ 接下来的第 $2$ 行到第 $N + 1$ （共 $N$ 行），每行为一个正整数，表示第i块披萨的大小， $1 \le i \le N$ 。披萨小块从某一块开始，按照一个方向次序顺序编号为 $1$ ~ $N$ ,每块披萨的大小范围为[$1,2147483647$]。

输出描述

”吃货“能分得到的最大的披萨大小的总和。

样例1

输入

5
8
2
10
5
7

输出

19

说明：

此例子中，有 $5$ 块披萨。每块大小依次为 $8$ 、$2$ 、$10$ 、$5$ 、$7$。按照如下顺序拿披萨，可以使”吃货拿到最多披萨:

1. “吃货”拿大小为 $10$ 的披萨
2. “馋嘴”拿大小为 $5$的披萨
3. “吃货”拿大小为 $7$ 的披萨
4. “馋嘴”拿大小为 $8$ 的披萨
5. ”吃货“拿大小为 $2$ 的披萨

至此，披萨瓜分完毕，”吃货“拿到的披萨总大小为 $10 + 7 + 2 = 19$

可能存在多种拿法，以上只是其中一种。