State machine DP (simple version)

Ah Fu is an experienced thief . Take advantage of the dark moon and the high wind , Ah Fu is going to rob a shop on the street tonight .

There are a total of  NN  Shops , There's some cash in every store .

Ah Fu investigated in advance and learned that , Only when he looted two adjacent shops at the same time , The alarm system on the street will start , Then the police will flock .

As a thief who has always committed crimes carefully , Ah Fu doesn't want to steal at the risk of being chased by the police .

He wants to know , Without alerting the police , The maximum amount of cash he can get tonight ？

Input format

The first line of input is an integer  TT, Means that there are  TT  Group data .

The next set of data , The first line is an integer  NN , Means that there are  NN  Shops .

The second line is  NN  A positive integer separated by spaces , Indicates the amount of cash in each store .

The amount of cash in each store does not exceed 1000.

Output format

For each set of data , Output one line .

This line contains an integer , It means the amount of cash a Fu can get without alerting the police .

Data range

1≤T≤501≤T≤50,
1≤N≤1051≤N≤105

sample input ：

2
3
1 8 2
4
10 7 6 14

sample output ：

8
24

Sample explanation

For the first set of samples , Ah Fu chooses the second 2 Shoplifting , The amount of cash received is 8.

For the second set of examples , Ah Fu chooses the second 1 and 4 Shoplifting , The amount of cash received is 10+14=24.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=1e5+5;
ll dp[N][2],a[N];
int t,n;
int main()
{
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof dp);
        memset(a,0,sizeof a);
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
            dp[i][1]=dp[i-1][0]+a[i];
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        }
        cout<<max(dp[n][1],dp[n][0])<<endl;
    }

    return 0;
}

Title Description

The big billed monkey found a magical Stonehenge in a row in the forest . Every night, several delicious bananas will appear on every boulder , When the sun rises , All bananas will disappear . The big billed monkey found a rule , If it takes away the bananas on the two adjacent boulders , Then Stonehenge will not produce bananas for a long time . The big billed monkey wants to know , You can eat bananas every night , The most bananas you can take away in a night .

Input

There are two lines of input
first line 1 A positive integer n, Indicates the number of boulders. The second line n Nonnegative integers , Space off , Indicates the number of bananas on each boulder stone[i]

Output

The output is one line
first line 1 It's an integer , It indicates the maximum number of bananas that the marmoset can take away in a night

The sample input  Copy

【 Examples 1】
4
5 3 7 2
【 Examples 2】
6
3 9 7 2 5 1

Sample output  Copy

【 Examples 1】
12
【 Examples 2】
15

Tips

Examples 1 explain ： take 1 Bananas on Boulder No ( Number of bananas = 5) , Then take it away 3 Bananas on Boulder No ( Number of bananas = 7). The maximum number of bananas that can be taken away in a night = 5 + 7 = 12 .

Examples 2 explain ： take 1 Bananas on Boulder No ( Number of bananas = 3), Then take it away 3 Bananas on Boulder No ( Number of bananas = 7), Then take it away 5 Bananas on Boulder No ( Number of bananas = 5). The maximum number of bananas that can be taken away in a night = 3 + 7 + 5 = 15 .

Data scope and conventions 0<n≤100,0≤stone[i]≤400

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int n;
ll a[105],dp[105][2];
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    dp[0][0]=0;
    dp[0][1]=0;
    for(int i=1; i<=n; i++)
    {
        dp[i][1]=dp[i-1][0]+a[i];
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
    }
    cout<<max(dp[n][1],dp[n][0]);

    return 0;
}