北华大学第五届程序设计竞赛春季联赛 D题

D-最大的收益
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述

一天，上课的时候小L老师带来一些食物，要把它分给同学们品尝，于是这些食物被分成了n堆。每一堆都给它标注了一个价值。
小L老师就问同学们如何选择品尝的顺序使得品尝的价值之和最大。聪明的你立马就想到了把所有的食物品尝一遍价值和就是最大。
这时小L老师立马加了一个规矩不能品尝相邻的两种食物，例如食物A B C依次摆放着桌子上，当你品尝了食物A 你就不能品尝食物B。
下一个品尝的食物只能是C。当你品尝了食物B，你就不能品尝食物C，同时也不能品尝食物A。聪明的你知道如何选择使得你从左到
右选择品尝的食物的价值最大嘛！最大的价值是多少。

输入描述:
第一行一个整数T（1≤T≤500），表示共有T组测试数据。
对于每组数据，第一次一个数字n（1≤n≤1000）表示有n堆食物接下来一行有n个数，分别表示每堆食物的价值ai (0≤ai≤100).

输出描述:
输出一个整数代表所能获得的最大价值

示例1

输入
2
4
1 2 3 4
3
2 3 0
输出

6
3
说明
样例一 选择品尝第二个和第四个食物获得的价值总和最大为6

思路：DP,在第i个位置有俩种选择，取，不取，取的话,那第i-1个就不能取 ，因此总价值就是dp[i-2] + a[i],不取的话，总价值就是dp[i-1]
以下是ac代码：

#include <iostream>
#include<cstdio>
using namespace std;

int a[1010];
int dp[1010];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
            dp[i] = 0;
        }
        dp[0] = 0;
        dp[1] = a[1];
        for(int i = 2; i <= n; i++){
            dp[i] = max(dp[i-2] + a[i], dp[i-1]);
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}