小牛一觉醒来发现自己来到了奇幻岛，奇幻岛上有很多山洞。小牛发现所有的山洞门白天都是关着的，到了晚上山洞门会自动打开。每天晚上当山洞门打开时，里面都有若干糖果。经过长时间观察小牛发现，如果他拿走相邻两个山洞的糖果，那么这两个山洞门会很多很多天不再打开。小牛希望所有的山洞每天晚上都能全部打开，那么他一晚上最多能拿走多少糖果。 输入格式 包含多组测试，每组测试数据包括两行。 第一行：一个整数n，代表山洞的数量（1<=n<=3000） 第二行：n个整数，代表每个山洞中糖果的数量（0<每个山洞中糖果数量<=500） 输出格式 每组测试输出一行，代表小牛一晚上最多能拿走的糖果数量（1<=糖果数量<=1500000）。用C语言来写

这是一道动态规划问题，可以使用类似于斐波那契数列的思路进行求解。设dp[i]表示前i个山洞中小牛最多能拿走的糖果数量，则有以下状态转移方程：

dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

其中nums[i-1]表示第i个山洞中的糖果数量，dp[i-1]表示小牛不拿第i个山洞中的糖果时前i-1个山洞中最多能拿走的糖果数量，dp[i-2]+nums[i-1]表示小牛拿第i个山洞中的糖果时前i-2个山洞中最多能拿走的糖果数量加上第i个山洞中的糖果数量。

最终答案为dp[n]。可以用一个一维数组dp来存储中间状态，时间复杂度为O(n)。

代码如下：

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int *nums = (int *) malloc(n * sizeof(int));
        int *dp = (int *) malloc((n + 1) * sizeof(int));
        for (int i = 0; i < n; i++) {
            scanf("%d", &nums[i]);
        }
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        printf("%d\n", dp[n]);
        free(nums);
        free(dp);
    }
    return 0;
}