大厂笔试模考_VC1 牛牛吃草

桃扇骨 2024-03-22 01:31 19阅读 0赞

#### 目录 ####

*   *  动态规划

![在这里插入图片描述][f1790e83f203424e8788e0934310e8d6.png]

### 动态规划 ###

*  1.确定dp数组以及下标的含义

wi\[i\]代表牛牛能吃到多少斤草  
ai\[i\]代表牛牛能走到哪隔吃草  
定义dp\[i\]为牛牛当前最多能吃到多少斤草

*  2.确定递推公式

dp[i] = Math.max(dp[i],dp[i]+temp);

temp是之前能走到dp\[i\]的最大值

*  3.dp数组如何初始化

初始化dp，将草地的斤数赋值给dp,因为牛牛可以从任何一块地开始

for(int i = 0;i < n ; i++){
        
                dp[i] = wi[i];
            }

*  4.确定遍历顺序

从题目可知，牛牛向右走的距离必须是ai的整数倍，所以遍历顺序从左到右

*  5.举例推导dp数组  
    ![在这里插入图片描述][98e4eda6fd754827b1d2aeef10884808.png]

代码实现

import java.util.Scanner;
    
    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int[] wi = new int[n];
            int[] ai = new int[n];
            //定义dp数组
            int[] dp = new int[n];
            for(int i = 0;i < n ; i++){
        
                wi[i] = in.nextInt();
            }
            for(int i = 0;i < n ; i++){
        
                ai[i] = in.nextInt();
            }
            //初始化dp，将草地的斤数赋值给do,因为牛牛可以从任何一块地开始
            for(int i = 0;i < n ; i++){
        
                dp[i] = wi[i];
            }
            for(int i = 0;i<n;i++){
        
                int temp = 0;
                for(int j = 0;j<i;j++){
        
                    //向右走的距离必须是ai的整数倍
                    if((i-j) % ai[j] == 0){
        
                       temp =  Math.max(dp[j],temp);
                    }
                }
                dp[i] = Math.max(dp[i],dp[i]+temp);
            }
            //答案不一定是在dp[n-1],可能是在中央
            int result = 0;
            for(int v : dp){
        
                result = Math.max(result,v);
            }
            System.out.println(result);
        }
    }

![在这里插入图片描述][1680dffc3013479cb54902832a24e551.png]

[f1790e83f203424e8788e0934310e8d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/56823a47f5fa4356a0863adeb2b127b8.png
[98e4eda6fd754827b1d2aeef10884808.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/eed7f1143be04ddc9ca0f11bade682bc.png
[1680dffc3013479cb54902832a24e551.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0fbfac513a2e409a87f66a1fe0063d8c.png