DP：地头蛇PIPI

朱雀 2023-10-06 20:44 13阅读 0赞

## DP：地头蛇PIPI ##

#### 文章目录 ####

*  DP：地头蛇PIPI
 *   *   *  问题
         *  思路
         *  代码

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

我们首先有一个自然而然的想法，我们设DP\[i\]为1~i这些商家能收取的最大保护费。但这样设状态我们不知道最后收取了到底是哪一家的保护费，不好进行状态的转移。因此，我们把DP\[i\]设为：一定收取了第i个商家保护费的情况下，1 ~ i这些商家能收取的最大保护费。收取了第i个商家的保护费，那么第i-1个商家的保护费就不能收取了，那么DP\[i\]看起来是从`DP[i-2],DP[i-3],…,DP[1]`这里面转移过来，但实际上DP\[i\]只能从DP\[i - 2\]或DP\[i - 3\]转移得到，因为对于第i - 2个商家和第i - 3个商家，我们总能收取其中一个的保护费，而且一定要收。举个例子，若DP\[i\]是从DP\[i-4\]转移，那么第i-1/i-2/i-3个商家的保护费都不收了。而我们完全可以多收第i-2个商家的保护费，为什么不选择多收呢？因此并不需要从i-2遍历到1选出最大值，i-2~1中的最大值必然是DP\[i-2\]与DP\[i-3\]其中之一。设a\[i\]表示从第i家商家收取的保护费，我们得到状态转移方程为：  
  `DP[i]=max(DP[i-2],DP[i-3])+a[i]`  
  最终答案就是DP\[n\]与DP\[n-1\]中的较大值

#### 代码 ####

import java.util.*;
    
    public class Main {
        
        static int[] dp = new int[100005];
        static int[] price = new int[100005];
        public static void main(String[] args) {
        
            int n, i;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                for (i = 0;i < n;i++) {
        
                    price[i] = scanner.nextInt();
                }
                dp[0] = price[0];
                if (n >= 2) {
        
                    dp[1] = price[1];
                }
                if (n >= 3) {
        
                    dp[2] = dp[0] + price[2];
                }
                for (i = 3;i < n;i++) {
        
                    dp[i] = Math.max(dp[i - 2], dp[i - 3]) + price[i];
                }
                System.out.println(n >= 2 ? Math.max(dp[n - 1], dp[n - 2]) : n >= 1 ? dp[n - 1] : 0);
            }
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/73b546317d2047379810f2852f6704c0.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/f4cc0287e52d44c0b59e92ee9495b95d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16