圆盘规律题

编程挑战：圆盘问题求解

问题描述：

有一个圆形盘面，分成了N个扇形区域，每个扇形区域有自己的分值，你需要选择任意数量的扇形区域，使得选择的扇形区域不相邻，且所有选中扇形区域的分值之和最大。请设计一种算法，求解这个问题。

输入：

第一行为一个整数N，表示圆形盘面上扇形区域的数量(1<=N<=100000)。

第二行为N个整数，表示每个扇形区域的分值。分值范围为1000到1000。

输出：

输出一个整数，表示该圆形盘面上任意数量的扇形区域的分值之和的最大值。

样例输入：

4

1 2 3 4

样例输出：

5

解题思路：

对于该问题，我们可以采用动态规划算法求解。假设dp[i]表示前i个扇形区域中，不选第i个扇形区域的最大分数，并且第i个扇形区域的左右相邻扇形区域都不选。那么最终的答案即为max(dp[N1],dp[N2])。

显然，当i=1时，dp[0]赋值为第0个扇形区域的分值，当i=2时，dp[1]的值为max(第0个扇形区域的分值，第1个扇形区域的分值)，两个扇形区域之间不能同时选中，选中两个中较大的那个分值。当i>2时，dp[i]的值既有选择第i个区域也有不选第i个区域两种情况：

不选第i个区域，则dp[i] = dp[i1]

选择第i个区域，则dp[i]=dp[i2] 第i个区域的分值;

综上，递推公式为dp[i] = max(dp[i1],dp[i2] 第i个扇形区域的分值)。

返回max(dp[N1],dp[N2])即可。

代码实现：

```python

N=int(input())

p=list(map(int,input().split()))

if N==1:

print(p[0])

else:

dp1=p[0]

dp2=max(p[0],p[1])

for i in range(2,N):

t=dp1 p[i]

dp1=dp2

dp2=max(dp2,t)

print(dp2)

```

本文 新鼎系統网 原创，转载保留链接！网址：https://acs-product.com/post/16681.html