AcWing 1049. 大盗阿福
原题链接
简单
作者:
小竹笋
,
2024-04-12 21:56:53
,
所有人可见
,
阅读 2
状态机的思想
f[i]表示洗劫前i家店铺的最大收益
状态表示:
f[i][0]表示未选最后的i
f[i][1]表示选择最后的i
所有走了i步,且当前位于状态j的所有走法
f[i][0]
(1)最后一步0->0 f[i-1][0]
(2)最后一步1->0 f[i-1][1]
f[i][1] ------ f[i-1][0]+w[i]
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5+10;
int n;
int a[N];
int f[N][2];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
f[0][0] = 0;
f[0][-1] = 0x3f3f3f3f;
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] + a[i];
}
printf("%d\n",max(f[n][0],f[n][1]));
}
return 0;
}