题目描述

fij代表第i家店的第j个状态，
0代表不选i店，1代表选择i店
注意0和1的状态转移

#include <iostream>

using namespace std;

const int N=100100;

//0表示没选这个店，1表示选了最后一个店
int f[N][2],a[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        f[0][0]=0;
        f[0][1]=-0x3f3f3f3f;
        for(int i=1;i<=n;i++)
        {
            //第i家店的0状态可由两个状态转移过来
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            //1状态只能由i-1的0状态转移过来
            f[i][1]=f[i-1][0]+a[i];

        }
        int res=0;
        for(int i=1;i<=n;i++)
        res=max(f[i][0],f[i][1]);
        cout<<res<<endl;
    }
    return 0;
}

2023/11/28

看过课之后，成功ac
fij：走了i步， 且当前状态位j的所有走法的最大值
f[i, 0]: 上一步是0； 上一步是1
f[i, 1]: 上一步是0
值得一提的是，状态机入口，为一个边界，设置为不可能取到的值

        // 状态机入口
        f[0][0]=0;
        f[0][1]=-0x3f3f3f3f;

#include <iostream>
#include <cstring>

using namespace std;

const int N=100010;
int f[N][2];
int n,T;
int a[N];

int main()
{
    cin>>T;
    while(T--)
    {
        memset(f, 0,sizeof(f));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }

        for(int i=1;i<=n;i++)
        {
            // 不偷第i家店
            f[i][0] = max(f[i-1][0], f[i-1][1]);

            // 偷第i家店
            f[i][1] = f[i-1][0] + a[i];

        }


        int res=0;
        for(int i=1;i<=n;i++)
        {
            res = max(res, f[i][0]);
            res = max(res, f[i][1]);
        }
        cout<<res<<endl;
    }

    return 0;
}