打家劫舍(二)

C++ 解法, 执行用时: 21ms, 内存消耗: 1176KB, 提交时间: 2022-03-16

#include <cstdio>
#include <vector>

int steal(std::vector<int> &nums, int st, int ed) {
    int post = 0, ppost = 0;
    int maxsum, ans = 0;
    for (int i = ed; i >= st; --i) {
        maxsum = std::max(post, nums[i] + ppost);
        ans = std::max(ans, maxsum);
        ppost = post;
        post = maxsum;
    }
    return ans;
}

int main() {
    int n;
    scanf("%d", &n);
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }
    printf("%d\n", std::max(steal(nums, 0, n - 2), steal(nums, 1, n - 1)));
    return 0;
}

C++ 解法, 执行用时: 21ms, 内存消耗: 1220KB, 提交时间: 2022-04-12

#include <bits/stdc++.h>

using namespace std;

int robRange(vector<int>& nums, int start, int end) {
		int first = nums[start], second = max(nums[start], nums[start + 1]);
		for (int i = start + 2; i <= end; i++) {
			int temp = second;
			second = max(first + nums[i], second);
			first = temp;
		}
		return second;
	}

	int rob(vector<int>& nums) {
		int length = nums.size();
		if (length == 1) {
			return nums[0];
		} else if (length == 2) {
			return max(nums[0], nums[1]);
		}
		return max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
	}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    cout << rob(v) << endl;
    return 0;
}

C++ 解法, 执行用时: 21ms, 内存消耗: 2060KB, 提交时间: 2022-07-22

#include <bits/stdc++.h>

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << a[0] << endl;
    }
    else if (n == 2) {
        cout << (a[0] > a[1] ? a[0] : a[1]) << endl;
    }
    else if (n == 3) {
        int temp = (a[0] > a[1] ? a[0] : a[1]);
        temp = (temp > a[2] ? temp : a[2]);
        cout << temp << endl;
    }
    else {
        int v[n];
        v[0] = a[2];
        v[1] = (a[2] > a[3] ? a[2] : a[3]);
        for (int i = 2; i < n - 3; i++) {
            v[i] = max(v[i - 1], v[i - 2] + a[i + 2]);
        }
        int result = v[n - 4] + a[0];
        v[0] = a[1];
        v[1] = max(a[1], a[2]);
        for (int i = 2; i < n - 1; i++) {
            v[i] = max(v[i - 1], v[i - 2] + a[i + 1]);
        }
        result = max(result, v[n - 2]);
        cout << result << endl;
    }
}

C++ 解法, 执行用时: 23ms, 内存消耗: 2112KB, 提交时间: 2022-04-22

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 2e5 + 5;
int n;
int arr[MAXN];
int dp[MAXN];
bool fg[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    int mmax = 0;
    dp[0] = arr[0], fg[0] = true;
    dp[1] = arr[1], fg[1] = false;
    dp[2] = dp[0] + arr[2], fg[2] = true;
    for(int i = 3; i < n; ++i){
        if(dp[i-2] > dp[i-3])
            dp[i] = dp[i-2], fg[i] = fg[i-2];
        else if(dp[i-2] < dp[i-3])
            dp[i] = dp[i-3], fg[i] = fg[i-3];
        else dp[i] = dp[i-2], fg[i] = fg[i-2] && fg[i-3];
        dp[i] += arr[i];
    }
    if(dp[n-1] > dp[n-2] && !fg[n-1])
        mmax = dp[n-1];
    else{
        mmax = dp[n-2];
        memset(dp, 0, sizeof(int) * n);
        dp[0] = 0;
        dp[1] = arr[1];
        dp[2] = arr[2];
        for(int i = 3; i < n; ++i){
            dp[i] = arr[i] + max(dp[i-2], dp[i-3]);
        }
        mmax = max(mmax, max(dp[n-1], dp[n-2]));
    }
        
    cout << mmax;

    return 0;
}

C++ 解法, 执行用时: 24ms, 内存消耗: 1160KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

/*
第一间房子和最后一间房子不能同时选
两次遍历，第一次求一定不选第一间房子的最大不相邻和
第二次求一定不选最后一间房子的最大不相邻和
两次较大值即为所求
*/
int main() {
    int n;
    cin >> n;
    int nums[n];
    int yes = 0, no = 0;
    cin >> nums[0];
    for (int i = 1; i < n; ++i) { // 一定不选第一间房子
        cin >> nums[i];
        int pre = no;
        no = max(no, yes);
        yes = pre + nums[i];
    }
    int res = max(yes, no);
    yes = no = 0;  // 重新计算一定不选最后一间的最大和
    for (int i = 0; i < n - 1; ++i) {
        int pre = no;
        no = max(no, yes);
        yes = pre + nums[i];
    }
    cout << max(res, max(yes, no)) << "\n";
    return 0;
}

详情