[白俊]#18427一緒に積み木

質問する

1番からN番までの学生はそれぞれいくつかのブロックがあります.各学生は最大M個のブロックを持つことができ、各学生が持つすべてのブロックの高さは異なる.このとき、1番からN番までの生徒たちは順番に自分の積み木を使い、地面から積み上げてタワーを形成します.
しかし、一部の学生のブロックは使用する必要がなく、学生ごとに最大1つのブロックしか使用できません.
1番からN番までの生徒の積み木についての情報があれば、高さHの塔を作ることができれば、数字を計算するプログラムを作成します.
例えば、N=3、M=3、H=5の場合、各生徒が持つブロックの高さは以下のように仮定される.

1番学生:2,3,5

2番学生:3、5、

3番学生:1、2、3

このとき、塔の高さを正確に5にするために、積み木の場合は以下の6種類がある.(ブロックを使用しない場合はXで表します.)

入力

1行目は、スペースを基準に自然数N,M,Hを分割します.(1≦N≦50,1≦M≦10,1≦H≦1000)2行目から,各学生が持つブロックの高さをスペースに準じて学生に区分する.
しかし,各ブロックの高さは1000以下の自然数であり,学生ごとに所有するすべてのブロックの高さは異なる.

しゅつりょく

最初の行にHの高さのタワーを作成すると、その数を10007で割って残りを出力します.

入力例1

3 3 5
2 3 5
3 5
1 2 3

サンプル出力1

6

に答える

この問題は動的プログラミングアルゴリズムで解決できる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int H = Integer.parseInt(input[2]);
        int[][] dp = new int[N+1][H+1];
        ArrayList<Integer>[] list = new ArrayList[N+1];
        for(int i=1; i<=N; i++)
            list[i] = new ArrayList<>();

        for(int i=1; i<=N; i++) {
            input = br.readLine().split(" ");

            for(int j=0; j<input.length; j++)
                list[i].add(Integer.parseInt(input[j]));
        }
        
        for(int i=0; i<=N; i++)   //0일 가능성은 모두 1이기 때문에
            dp[i][0] = 1;

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=H; j++) {
                
                for(int x : list[i]) {
                    if(j>=x) {
                        dp[i][j] += dp[i-1][j-x] %= 10007;  //해당 블록을 쌓을수 있는 경우 더해줌
                    }
                }

                dp[i][j] += dp[i-1][j] %= 10007;  //블록을 안쌓을 경우
            }
        }

        System.out.println(dp[N][H]%10007);
    }
}