题目描述
最直白的做法,last_undo表示上一家不偷,last_do表示上一家偷,now_do表示这家偷,now_undo表示这家不偷
每次结尾继承上一家是的状态即可
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],T,n;
int main(){
cin>>T;
while(T--){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int last_undo=0,last_do=a[1],now_undo=0,now_do=0;
for(int i=2;i<=n;i++){
now_do=last_undo+a[i];
now_undo=max(last_undo,last_do);
last_do=now_do;
last_undo=now_undo;
}
cout<<max(last_undo,last_do)<<endl;
}
}