1049 大盗阿福

• 状态表示：f[i] 表示从第 1 家店到第 i 家店打劫的所有方案，存储的值即为最高价值
• 状态转移：以最后一次的行为作为划分依据，分为 打劫第 i 家店 和 不打劫第 i 家店。状态转移方程为f[i] = max(f[i - 1], f[i - 2] + w[i])
  • 打劫第 i 家店：那么状态可以从f[i - 2] 转移过来，需要再加上w[i];
  • 不打劫第 i 家店：那么状态可以从f[i - 1]转移过来

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e5 + 10;
int w[N], f[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 ++ ) cin >> w[i];
        f[1] = w[1];
        for (int i = 2; i <= n; i ++ )
            f[i] = max(f[i - 1], f[i - 2] + w[i]);

        cout << f[n] << endl;
    }
    return 0;
}