从一堆n个编号分别为1,2……n的糖果中选择任意多个糖果,设定一个限制:如果选择了编号为i 的糖果,就不能选择编号为i -1,i-2,i +1,i +2的四个糖果了,每个糖果都有一个对应的美味值,请选出糖果美味值之和最大的?输入描述:第一行一个整数n,表示糖果数量,第二行n个整数a1,a2…..an,其中ai 表示编号为i的糖果的美味值。请写出这道算法题目的Java 代码
时间: 2023-05-26 22:07:22 浏览: 94
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n+1];
for(int i=1;i<=n;i++){
a[i] = sc.nextInt();
}
int[] dp = new int[n+1];
dp[1] = a[1];
if(n>1){
dp[2] = Math.max(a[1],a[2]);
}
for(int i=3;i<=n;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+a[i]);
}
System.out.println(dp[n]);
}
}
```
注:本题本质上是一道动态规划问题。dp[i]表示前i个糖果中选择糖果满足限制条件的最大美味值和。当选择i号糖果时,之前的选择要么是dp[i-2],要么是dp[i-3],所以dp[i]的值应该由这两者的较大值加上i号糖果的美味值。否则,如果不选择i号糖果,那么dp[i]就等于dp[i-1]。最终,我们需要返回dp[n]作为答案。