#P3040. 分披萨(100分)
-
1000ms
Tried: 332
Accepted: 31
Difficulty: 8
所属公司 :
华为od
分披萨(100分)
思路:动态规划
问题
- 披萨切片:披萨被切成
N(奇数)个大小各不相同的切片。 - 分配规则:
- 第一步:“吃货”可以任意选择一个切片。
- 之后:两人轮流从当前剩余披萨的两端(左端或右端)选择切片。
- “馋嘴”策略:每次总是选择当前两端中较大的切片。
- 目标:计算“吃货”能够获得的最大披萨总大小。
解决思路
-
线性化披萨切片:由于披萨是圆形的,我们需要考虑所有可能的起始点。对于每一个起始点,将披萨切片线性化,便于应用动态规划。
-
动态规划表
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]的值为“吃货”选择左端或右端后的最大值。
- 定义
-
遍历所有起始点:对于每一个可能的起始点,计算“吃货”在该起始点下能够获得的最大披萨总大小,最终取所有起始点中的最大值。
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≤N<500 接下来的第 2 行到第 N+1 (共 N 行),每行为一个正整数,表示第i块披萨的大小, 1≤i≤N 。披萨小块从某一块开始,按照一个方向次序顺序编号为 1 ~ N ,每块披萨的大小范围为[1,2147483647]。
输出描述
”吃货“能分得到的最大的披萨大小的总和。
样例1
输入
5
8
2
10
5
7
输出
19
说明:
此例子中,有 5 块披萨。每块大小依次为 8 、2 、10 、5 、7。按照如下顺序拿披萨,可以使”吃货拿到最多披萨:
- “吃货”拿大小为 10 的披萨
- “馋嘴”拿大小为 5的披萨
- “吃货”拿大小为 7 的披萨
- “馋嘴”拿大小为 8 的披萨
- ”吃货“拿大小为 2 的披萨
至此,披萨瓜分完毕,”吃货“拿到的披萨总大小为 10+7+2=19
可能存在多种拿法,以上只是其中一种。