当前位置：网站首页>[dynamic planning]dp24 house raiding (II) - medium

[dynamic planning]dp24 house raiding (II) - medium

2022-07-19 00:14:00 【51CTO】

DP24 raid homes and plunder houses ( Two )

describe

You are an experienced thief , Ready to steal a row of rooms along the lake , Each room has a certain amount of cash , To prevent detection , You can't steal two neighboring houses , namely , If you steal the first one , You can't steal a second house , If you steal a second house , Then you can't steal the first and third . The rooms along the lake form a closed circle , That is, the first room and the last room are considered adjacent .

Given a length of n Array of integers for nums, The elements in the array represent the amount of cash in each room , Please calculate the maximum amount of theft without being found .

Data range ： The array length satisfies , Each value in the array satisfies

Input description ：

Enter a positive integer in the first line n , Represents the length of an array .

Second line input n A positive integer , Indicates the cash stored in each room .

Output description ：

Output the most stolen amount

Example 1

Input ：

Output ：

explain ：

       
        The best solution is to steal the second  2 4  A room 
      
1.

Example 2

Input ：

Output ：

explain ：

       
        because  1  and  3  It's adjacent , Therefore, the best solution is to steal the second  3  A room 
      
1.

Answer key

Dynamic programming solution

       
       #include <bits/stdc++.h>
       
       int 
       
       solve(
       
       const 
       
       std::vector
       
       <
       
       int
       
       > 
       
       &
       
       v)
       
{
       
       if (
       
       v.
       
       size() 
       
       == 
       
       0)
       
  {
       
       return 
       
       0;
       
  }
       
       if (
       
       v.
       
       size() 
       
       == 
       
       1)
       
  {
       
       return 
       
       v[
       
       0];
       
  }
       
       std::vector
       
       <
       
       int
       
       > 
       
       dp(
       
       v.
       
       size(), 
       
       0);
       
       //  Just take the head , Don't take the tail 
       
       dp[
       
       0] 
       
       = 
       
       v[
       
       0];
       
       dp[
       
       1] 
       
       = 
       
       std::max(
       
       v[
       
       0], 
       
       v[
       
       1]);
       
       for (
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       < 
       
       v.
       
       size() 
       
       - 
       
       1; 
       
       ++
       
       i)
       
  {
       
       dp[
       
       i] 
       
       = 
       
       std::max(
       
       dp[
       
       i 
       
       - 
       
       1], 
       
       dp[
       
       i 
       
       - 
       
       2] 
       
       + 
       
       v[
       
       i]);
       
  }
       
       int 
       
       ans 
       
       = 
       
       dp[
       
       v.
       
       size() 
       
       - 
       
       2];
       
       //  Tail only , Don't take the head 
       
       dp[
       
       0] 
       
       = 
       
       0;
       
       dp[
       
       1] 
       
       = 
       
       v[
       
       1];
       
       for (
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       < 
       
       v.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       dp[
       
       i] 
       
       = 
       
       std::max(
       
       dp[
       
       i 
       
       - 
       
       1], 
       
       dp[
       
       i 
       
       - 
       
       2] 
       
       + 
       
       v[
       
       i]);
       
  }
       
       return 
       
       std::max(
       
       ans, 
       
       dp.
       
       back());
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n;
       
       std::cin 
       
       >> 
       
       n;
       
       std::vector
       
       <
       
       int
       
       > 
       
       v(
       
       n);
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       ++
       
       i)
       
  {
       
       std::cin 
       
       >> 
       
       v[
       
       i];
       
  }
       
       std::cout 
       
       << 
       
       solve(
       
       v) 
       
       << 
       
       std::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.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.