题目描述

大盗阿笨要去偷东西。偷的商家不能是连续两个，问最终偷得到多少钱。

样例

略……

算法1

暴力+dp

时间复杂度 $O(t*n)$

emmmm……
这题应该是挺简单的，下面开始讲思路。

1.首先，要来个特判：如果只有一个数，那就输出他。
2.接着，用for开始dp式暴力：

for(2~n)
{
    输入
    给dp数组赋值：为i-2个及之前最大值maxx+当前输入值
    取出最大值sum
    取出前i-1个中的最大值maxx    
}

C++ 代码

#include<iostream>
using namespace std;
int n,t,ans,maxx;
int a[100010],f[100010];
int main()
{
    cin>>t;
    for(int kkk=1; kkk<=t; kkk++)
    {
        cin>>n;
        cin>>a[1];
        maxx=0;
        ans=0;
        if(n==1)
        {
            cout<<a[1]<<endl;
            continue;
        } 
        f[1]=a[1];
        ans=a[1];
        for(int i=2; i<=n; i++)
        {
            cin>>a[i];
            f[i]=a[i]+maxx;
            ans=max(ans,f[i]);
            maxx=max(maxx,f[i-1]);
        }
        cout<<ans<<endl;
    }
}