ac.1049.大盗阿福 - 凌冬的个人博客

ac.1049大盗阿福

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 $N$ 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？输入格式输入的第一行是一个整数 $T$，表示一共有 $T$ 组数据。接下来的每组数据，第一行是一个整数 $N$ ，表示一共有 $N$ 家店铺。第二行是 $N$ 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。输出格式对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。数据范围

$1 \le T \le 50$, $1 \le N \le 10^5$

输入样例：

2 3 1 8 2 4 10 7 6 14

输出样例：

8 24

样例解释对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。

解题思路

不能同时偷两个银行

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

const int MAXN = 1e5+10;
const int MAXT = 51;
int n,a[MAXN] , dp[MAXN][2];
int t;
int main()
{
    cin>>t;
    while(t--) {
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        
        for(int i=1;i<=n;i++) {
            //隔着偷  dp[i] = max(dp[i-1],dp[i-2] + value[i])
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0] + a[i];
             
        }
        
        cout << max(dp[n][1],dp[n][0]) <<endl;
        
        
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here
        int n =nums.size();
        if(n<=0) return 0;
        if(n==1) return nums[0];
        vector<int> dp(n+1);
        // dp[i] = max(dp[i-1],dp[i-2] + nums[i]) ,到 i为止最大利益
        dp[0] = 0;//什么都不偷
        dp[1] = nums[0];
        int res = 0;
        for(int i=2;i<=n;i++) {
            dp[i]  =  dp[i-1];//不偷当前的
            if(i>=2) {
                dp[i] = max(dp[i],dp[i-2] + nums[i-1]);
            }
            res = max(res,dp[i]);
        }
        return res;
    }
};

环形打家劫舍

描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
        // write code here,环形, 第1家和最后一家不能同时偷
        // for 1-> n-2
        // for 2-> n-1
        int n = nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        vector<int> dp(n+1,0);
        dp[0] = 0;dp[1] = nums[0];
        int res = 0;
        for(int i=2;i<=n-1;i++) {
            dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);//偷和不偷选一个最大的 记录
        }
        res = dp[n-1];
        dp[0] = dp[1] = dp[2] = 0;
        //从3开始
        dp[0] = 0, dp[1] = 0;
        dp[2] = nums[1];//从1开始偷
        for(int i=3;i<=n;i++) {
             dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);//偷和不偷选一个最大的 记录
        }
        return max(res,dp[n]);
        
    }
};

文章目录