做博客网站赚钱,中国物联网企业排名,网站设计的公司如何选,沭阳县城乡建设局网站#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1067 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图 披萨大作战题目描述输入格式输出格式样例输入样例输出数据范围题解参考代码 披萨大作战
题目描述
K小姐和A先生到披萨店点了一份圆形披萨,并嘱咐店员将披萨切成大小相同的偶数块。但是粗心的服务员把披萨切成了大小不一的 N N N 块,且 N N N 为奇数。
为了公平起见,两人商量了一个取披萨的规则:从K小姐开始,轮流取披萨。除了第一块披萨可以随意选取外,其余的披萨必须从上一个人取完的披萨的相邻位置开始取。
A先生每次都会选择剩下披萨中最大的一块,而K小姐知道A先生的这个特点。现在给定每块披萨的大小,请问K小姐最多能够取到多少大小的披萨呢?
输入格式
第一行包含一个正整数 N N N,表示披萨被切成了 N N N 块。
接下来 N N N 行,每行一个正整数,第 i i i 行的整数表示第 i i i 块披萨的大小 A i A_i Ai。
输出格式
输出一个整数,表示K小姐最多能够取到的披萨大小之和。
样例输入
5
8
2
10
5
7样例输出
19数据范围 3 ≤ N 500 3 \le N 500 3≤N500,保证 N N N 为奇数 1 ≤ A i ≤ 2147483647 1 \le A_i \le 2147483647 1≤Ai≤2147483647
题解
本题可以使用记忆化搜索来解决。
定义 s o l v e ( L , R ) solve(L,R) solve(L,R) 表示当前还剩下第 L L L 块到第 R R R 块披萨时,K小姐能够取到的最大披萨大小之和。那么答案就是 m a x ( s o l v e ( ( i 1 ) m o d N , ( i − 1 N ) m o d N ) A i ) max(solve((i1) \bmod N, (i-1N) \bmod N) A_i) max(solve((i1)modN,(i−1N)modN)Ai),其中 0 ≤ i N 0 \le i N 0≤iN。
对于函数 s o l v e ( L , R ) solve(L,R) solve(L,R),我们可以分情况讨论: 如果 L R L R LR,那么只剩下一块披萨,K小姐直接取走,因此 s o l v e ( L , R ) A L solve(L,R) A_L solve(L,R)AL。 如果 L ≠ R L \neq R LR,那么A先生会取走两端披萨中较大的一块。设 L ′ L L′ 和 R ′ R R′ 分别表示取走披萨后的左右端点,那么有: 如果 A L A R A_L A_R ALAR,那么 L ′ ( L 1 ) m o d N , R ′ R L (L1) \bmod N, R R L′(L1)modN,R′R如果 A L ≤ A R A_L \le A_R AL≤AR,那么 L ′ L , R ′ ( R − 1 N ) m o d N L L, R (R-1N) \bmod N L′L,R′(R−1N)modN 因此 s o l v e ( L , R ) m a x ( A L s o l v e ( L ′ , R ) , A R s o l v e ( L , R ′ ) ) solve(L,R) max(A_L solve(L, R), A_R solve(L, R)) solve(L,R)max(ALsolve(L′,R),ARsolve(L,R′))。
为了避免重复计算,我们可以使用记忆化数组 d p dp dp 来保存已经计算过的状态。其中 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示当前还剩下第 i i i 块到第 j j j 块披萨时,K小姐能够取到的最大披萨大小之和。
时间复杂度 O ( N 2 ) O(N^2) O(N2),空间复杂度 O ( N 2 ) O(N^2) O(N2)。
参考代码
Python
N int(input())
A [int(input()) for _ in range(N)]
dp [[-1] * N for _ in range(N)]def solve(L, R):if A[L] A[R]:L (L 1) % Nelse:R (R - 1 N) % Nif dp[L][R] ! -1:return dp[L][R]if L R:dp[L][R] A[L]else:dp[L][R] max(A[L] solve((L1)%N, R), A[R] solve(L, (R-1N)%N))return dp[L][R]ans 0
for i in range(N):ans max(ans, solve((i1)%N, (i-1N)%N) A[i])print(ans)Java
import java.util.Scanner;public class Main {static int N;static int[] A;static int[][] dp;public static void main(String[] args) {Scanner sc new Scanner(System.in);N sc.nextInt();A new int[N];for (int i 0; i N; i) {A[i] sc.nextInt();}dp new int[N][N];for (int i 0; i N; i) {for (int j 0; j N; j) {dp[i][j] -1;}}int ans 0;for (int i 0; i N; i) {ans Math.max(ans, solve((i1)%N, (i-1N)%N) A[i]);}System.out.println(ans);}static int solve(int L, int R) {if (A[L] A[R]) {L (L 1) % N;} else {R (R - 1 N) % N;}if (dp[L][R] ! -1) {return dp[L][R];}if (L R) {dp[L][R] A[L];} else {dp[L][R] Math.max(A[L] solve((L1)%N, R), A[R] solve(L, (R-1N)%N));}return dp[L][R];}
}Cpp
#include iostream
#include vector
#include cstring
#include algorithm
using namespace std;const int N 500;
int n, a[N], dp[N][N];int solve(int L, int R) {if (a[L] a[R]) {L (L 1) % n;} else {R (R - 1 n) % n;}if (dp[L][R] ! -1) {return dp[L][R];}if (L R) {dp[L][R] a[L];} else {dp[L][R] max(a[L] solve((L1)%n, R), a[R] solve(L, (R-1n)%n));}return dp[L][R];
}int main() {cin n;for (int i 0; i n; i) {cin a[i];}memset(dp, -1, sizeof(dp));int ans 0;for (int i 0; i n; i) {ans max(ans, solve((i1)%n, (i-1n)%n) a[i]);}cout ans endl;return 0;
}
