状态机模型就是将所有的转移方式简化成若干个状态之间的相互转化
01表示当前店铺是否打劫,因为不能连续打劫,所以1只能从1转移,
0可以从0或1转移表示在当前店铺不打劫的情况下上个店铺打劫与否都可以
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int f[N][2],w[N];
int T,n;
int main(){
cin>>T;
while(T--){
cin>>n;
//入口的设置方式很灵活 都设为零也可以
f[0][0]=0,f[0][1]=-INF; //表示不能选 设置虚拟入口
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++){
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=f[i-1][0]+w[i];
}
cout<<max(f[n][0],f[n][1])<<endl;
}
return 0;
}