题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int T,N;

/*
f[i][j]表示第i间商铺是否被盗 j取值为0/1
递推公式： f[i][0] = max(f[i - 1][0] , f[i-1][1]); 第i间不被盗 <-- 第i-1间不被盗 / 第i-1间被盗  转化而来
           f[i][1] = f[i - 1][0] + nums[i]; 
*/

int main(){
    cin >> T;
    while(T--){
        cin >> N;
        vector<int> nums(N);
        for(int i = 0 ; i < N ; i++){
            cin >> nums[i];
        }
        vector<vector<int> > f(N ,(vector<int> (2)));
        //分两种情况1.盗第一家 2.不盗第一家
        f[0][0] = 0 , f[0][1] = nums[0];
        for(int i = 1 ; i < N ; i++){
            f[i][0] = max(f[i - 1][1], f[i - 1][0]);
            f[i][1] = f[i - 1][0] + nums[i];
        }
        int res = max(f[N - 1][0],f[N - 1][1]);
        cout << res << endl;
    }
}