D最大的收益

DP
因为对一个数，我们有两个选择，一个表示这个数选了，一个表示没有选。
如果上一个没有选，那么当前的选或者不选都可以，所以我们取大的值；
如果上一个选了并且当前想要去选的话，那么我们要选择上一个没选过的来加上了；

设当没选了的最优的是：f[i][0]
当前选了的最优的是: f[i][1]
所以状态转移方程：
f[i][0] = max{f[i-1][0],f[i-1][1]}
f[i][1] = f[i-1][0]+a[i];

#include <bits/stdc++.h>
using namespace std;
int f[10001][10]={0};
int main()
{
    int T;
    int n;
    int a[10001];
    scanf("%d",&T);
    int ans;
    while(T--)
    {
        scanf("%d",&n);
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }        
        //初始的状态，选的和没选的
        f[1][0]=0; 
        f[1][1]=a[1];
        for(int i=2;i<=n;i++)     //状态转移方程
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][0]+a[i];
        }    
        ans=max(f[n][0],f[n][1]);     //取最大的
        printf("%d\n",ans);
    }    
    return 0;
}