E卷-分披萨-(100分)

分披萨

题目描述

K小姐和A先生到披萨店点了一份圆形披萨,并嘱咐店员将披萨切成大小相同的偶数块。但是粗心的服务员把披萨切成了大小不一的 块,且 为奇数。

为了公平起见,两人商量了一个取披萨的规则:从K小姐开始,轮流取披萨。除了第一块披萨可以随意选取外,其余的披萨必须从上一个人取完的披萨的相邻位置开始取。

A先生每次都会选择剩下披萨中最大的一块,而K小姐知道A先生的这个特点。现在给定每块披萨的大小,请问K小姐最多能够取到多少大小的披萨呢?

输入格式

第一行包含一个正整数 ,表示披萨被切成了 块。

接下来 行,每行一个正整数,第 行的整数表示第 块披萨的大小 。

输出格式

输出一个整数,表示K小姐最多能够取到的披萨大小之和。

样例输入

5
8
2
10
5
7

样例输出

19

数据范围

• ,保证 为奇数
• 

题解

动态规划

本题可以使用记忆化搜索来解决。

定义 表示当前还剩下第 块到第 块披萨时,K小姐能够取到的最大披萨大小之和。那么答案就是 ,其中 。

对于函数 ,我们可以分情况讨论:

1. 如果 ,那么只剩下一块披萨,K小姐直接取走,因此 。

2. 如果 ,那么A先生会取走两端披萨中较大的一块。设 和 分别表示取走披萨后的左右端点,那么有:

   • 如果 ,那么
   • 如果 ,那么

   因此 。

为了避免重复计算,我们可以使用记忆化数组 来保存已经计算过的状态。其中 表示当前还剩下第 块到第 块披萨时,K小姐能够取到的最大披萨大小之和。

时间复杂度 ,空间复杂度 。

参考代码

• Python

# 读取输入
N = int(input())
A = [int(input()) for _ in range(N)]

# 初始化dp数组
dp = [[-1] * N for _ in range(N)]

def solve(L, R):
    # A先生取走较大的一块披萨
    if A[L] > A[R]:
        L = (L + 1) % N
    else:
        R = (R - 1 + N) % N
    
    # 如果已经计算过这种情况，直接返回结果
    if dp[L][R] != -1:
        return dp[L][R]
    
    # 如果只剩一块披萨，K小姐直接取走
    if L == R:
        dp[L][R] = A[L]
    else:
        # K小姐选择能使自己获得最大值的方案
        dp[L][R] = max(A[L] + solve((L+1)%N, R), A[R] + solve(L, (R-1+N)%N))
    
    return dp[L][R]

# 计算K小姐能获得的最大披萨大小
ans = 0
for i in range(N):
    ans = max(ans, solve((i+1)%N, (i-1+N)%N) + A[i])

# 输出结果
print(ans)

• C

#include <stdio.h>
#include <string.h>

#define MAX_N 510
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int N, A[MAX_N];
long long dp[MAX_N][MAX_N];

long long solve(int L, int R) {
    // A先生取走较大的一块披萨
    if (A[L] > A[R]) {
        L = (L + 1) % N;
    } else {
        R = (R - 1 + N) % N;
    }

    // 如果已经计算过这种情况，直接返回结果
    if (dp[L][R] != -1) {
        return dp[L][R];
    }

    // 如果只剩一块披萨，K小姐直接取走
    if (L == R) {
        dp[L][R] = A[L];
    } else {
        // K小姐选择能使自己获得最大值的方案
        dp[L][R] = MAX(A[L] + solve((L+1)%N, R), A[R] + solve(L, (R-1+N)%N));
    }

    return dp[L][R];
}

int main() {
    // 读取输入
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    // 初始化dp数组
    memset(dp, -1, sizeof(dp));

    // 计算K小姐能获得的最大披萨大小
    long long ans = 0;
    for (int i = 0; i < N; i++) {
        ans = MAX(ans, solve((i+1)%N, (i-1+N)%N) + A[i]);
    }

    // 输出结果
    printf("%lld\n", ans);

    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInte