状态机模型就不说了 主要想练习一下动态规划的思想
根据闫氏dp思想 首先划分集合. f[i] 表示必须要偷第i个商铺，那么f[i] 可以由 f[0],…f[i - 2] 转移过来
f[i] = max(f[j] + w[i]) (0 <= j < i - 1)
代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int f[N],w[N];
int main()
{
    int T; cin >> T;
    while( T--)
    {
        memset(f, 0, sizeof f);
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) scanf("%d",&w[i]);
        f[1] = w[1];
        int ans = f[1];
        for(int i = 2; i <= n; ++i) 
        {
            for(int j = 0; j < i - 1; ++j)
                f[i] = max(f[i], f[j] + w[i]); 
            ans = max(ans, f[i]);
        }
        cout << ans << '\n';

    }
}

然后因为n是10000 两层for循环会超时 然后想办法优化一下
我们发现f[i] 其实是由max(f[j] (0 <= j < i - 1)) 转移过来的. 然后我们类比最长上升子序列那个优化的思想，保存一下前i-1个f[j]的最大值，更新就可

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int f[N],w[N];
int main()
{
    int T; cin >> T;
    while( T--)
    {
        memset(f, 0, sizeof f);
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) scanf("%d",&w[i]);
        f[1] = w[1];
        int ans = f[1];
        int maxv = w[0];
        for(int i = 2; i <= n; ++i) 
        {
            f[i] = max(f[i], maxv + w[i]); 
            maxv = max(maxv,f[i - 1]);
            ans = max(ans, f[i]);
        }
        cout << ans << '\n';

    }
}