2016 蓝桥杯预选赛

╰+哭是因爲堅強的太久メ 2022-06-17 01:11 275阅读 0赞

*   *   *  通往图书馆的楼梯
         *  塞不下的背包

--------------------

### 通往图书馆的楼梯 ###

**【问题描述】**

Mr. Chen 决定去图书馆复习,上图书馆需要爬好多级台阶。

Mr. Chen 可以一步跨两级，也可以一级一级走。他突然想到一个问题,对于这段共 N 级的楼梯，若每次只能跨一级或二级，要走上第 N 级，共有多少种走法？

**【输入格式】**

输入共 N+1 行，第一行为一个整数 T，表示共有 T 组数据，接下来 T 行，每行包含一个整数 N，表示楼梯的级数。

**【输出格式】**

输出包括 T 行，为每一个 N 对应的走法数目。

**【样例输入】**

> 3  
> 1  
> 2  
> 5  
> 9

**【样例输出】**

> 1  
> 2  
> 8

**【数据规模与约定】**

对于 100%的数据，1 ≤ T ≤ 10000000 ,1 ≤ N ≤ 40。

**【解题代码】**

import java.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int[] a = new int[41];
            a[0] = a[1] = 1;
            for (int i = 2; i < a.length; i++)
                a[i] = a[i - 1] + a[i - 2];
            int T = sc.nextInt();
            while (T-- > 0) {
                int n = sc.nextInt();
                System.out.println(a[n]);
            }
        }
    }

--------------------

### 塞不下的背包 ###

**【问题描述】**

Mr. Chen 要和 Mrs. Chen 一起去北京旅游了。出发前 Mrs. Chen 准备带好多好多零食。不过很可惜他们的背包容量是有限的，并不能把所有准备的零食都带走。Mrs. Chen 需要作出抉择。

每件零食都有三个参数，质量Wi ，体积Vi ，以及 Mrs. Chen 对它的喜爱程度 Si 。已知背包最大的承载质量为 W，体积为 V，那么，Mrs. Chen 该如何选择，才能使得总的喜爱程度 S(= ∑ Si) 最大呢？

**【输入格式】**

输入共 N+1 行。第一行包含三个整数 N W V，分别表示零食的总数，背包的最大承载质量，背包的容积。

接下来 N 行，每行有三个整数Wi ，Vi ，Si ，每两个整数之间用一个空格隔开，分别表示第i 个物品的质量，体积以及 Mrs. Chen 的喜爱程度。

**【输出格式】**

输出仅一行，包含一个整数，为喜爱程度和 S 最大可能达到的值。

**【样例输入】**

> 5 20 15  
> 18 13 70  
> 6 6 30  
> 12 8 48  
> 5 7 29  
> 9 12 51

**【样例输出】**

> 78

**【数据规模与约定】**

> 对于 100%的数据，有1 ≤ n ≤ 1000000 ，1 ≤ Wi ≤ 1000 ，1 ≤ Vi ≤ 1000 ，1 ≤ W, V ≤ 10000000 。

**【解题代码】**

import java.util.Scanner;
    
    public class Main { 
    
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            String[] tmp = sc.nextLine().split(" ");
            int N = Integer.parseInt(tmp[0]);
            int W = Integer.parseInt(tmp[1]);
            int V = Integer.parseInt(tmp[2]);
            int[] w = new int[N];
            int[] v = new int[N];
            int[] s = new int[N];
            for (int i = 0; i < N; i++) {
                tmp = sc.nextLine().split(" ");
                w[i] = Integer.parseInt(tmp[0]);
                v[i] = Integer.parseInt(tmp[1]);
                s[i] = Integer.parseInt(tmp[2]);
            }
            int[][] dp = new int[W + 1][V + 1];
            for (int i = 0; i < N; i++)
                for (int j = W; j >= w[i]; j--)
                    for (int k = V; k >= v[i]; k--)
                        dp[j][k] = Math.max(dp[j][k], dp[j - w[i]][k - v[i]] + s[i]);
            System.out.println(dp[W][V]);
        }
    }