3.27 网易春招第一题--击杀怪物

目录

• 题目描述
• 输入描述
• 输出描述
• 参考方法

题目描述

小红在一个游戏里杀怪。这是个回合制游戏，小红和两只怪物相遇了。
第一只怪物有 a 血量，第二只怪物有 b血量。
小红有两个技能：
第一个技能叫火球术，效果是对单体怪物造成 x 伤害。
第二个技能叫烈焰风暴，效果是对每只怪物造成 y伤害。
小红想知道，自己最少使用多少次技能，可以击杀这两只怪物。
（当怪物血量小于等于0时，视为被击杀）

输入描述

四个正整数a , b , x , y 用空格隔开。
1 < a , b , x , y < 20

输出描述

小红使用技能的最少次数。
示例1

输入
5 2 3 1
输出
3

参考方法

两种方法测试无问题
第一种方法参考：https://blog.csdn.net/weixin_45619734/article/details/123777226
采用分情况讨论。

第二种方法参考：动态规划
完全背包与二维背包问题的结合，采用顺序遍历的方法

采用了压缩数组！
关键点：
1、一个物体都放不下
dp[j][k] = Math.min(dp[j][k],1);
2、可以放下
dp[j][k] = Math.min(dp[j][k], dp[x1][y1] + 1);

package wangyi;

import java.util.Scanner;

public class wangyi327 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();  //条件一
        int b = scanner.nextInt();  //条件二

        int x = scanner.nextInt();
        int y = scanner.nextInt();

//        int a = 5;
//        int b = 2;
//        int x = 1;
//        int y = 2;

        int[] wupingone = new int[4];
        int[] wupingtwo = new int[4];



        wupingone[0] = 0;
        wupingone[1] = y;
        wupingone[2] = x;
        wupingone[3] = 0;

        wupingtwo[0] = 0;
        wupingtwo[1] = y;
        wupingtwo[2] = 0;
        wupingtwo[3] = x;

        int[][] dp = new int[a + 1][b + 1];

        //初始化
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < a + 1; j++) {
                for (int k = 0; k < b + 1; k++) {
                    dp[j][k] = 0x3f3f3f3f; //取一个较大数值
                }
            }
        }
        dp[0][0] = 0;  //注意0 0 这个条件


        //动态转移公式   完全二维背包
        for (int i = 1; i <= 3; i++) {
            for (int j = 0; j < a + 1; j++) {
                for(int k = 0; k < b + 1; k++) {
                    //完全二维背包  不取  取该物品
                    if(j < wupingone[i] && k < wupingtwo[i]){
                        //比该物品小时  与1比较
                        dp[j][k] = Math.min(dp[j][k],1);
                    }else {
                        //注意点！ 可能相减为负数
                        int x1 = 0;
                        int y1 =0;
                        if(j-wupingone[i] < 0){
                            x1 = 0;
                        }else{
                            x1 = j-wupingone[i];
                        }

                        if(k - wupingtwo[i] < 0 ){
                            y1 =0;
                        } else{
                            y1 = k - wupingtwo[i];
                        }
                        //动态转移方程  与上一次的比较   或者与新更新的比较  所以采用顺序
                        //参考完全背包问题  采用顺序！！！！  并且参考二维背包问题！！！
                        dp[j][k] = Math.min(dp[j][k], dp[x1][y1] + 1);
                    }
                }
            }
        }
        System.out.println(dp[a][b]);
    }
}