[白俊](Java)14501-退社

質問リンク

https://www.acmicpc.net/problem/14501

問題を解く

徹底した探索を通じて、最大の価値に近づいた.
勤務日とお金が書かれたCounsel類を作成しました.
探索の開始はbf(0)から始まり,パラメータとしてarraylistを反復して用いた.
基本的なdfsのように、一度アクセスしたインデックスは聞こえません.
条件が合えばArraylistに入れます.
インデックスを値が含まれている時間に増やし、次の再帰に移動します.

        for (int i = idx; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            res.add(new Counsel(counselList.get(i).time, counselList.get(i).money));
            chk[i] = true;
            bf(i + counselList.get(i).time, res);
            res.remove(res.size() - 1);
            chk[i] = false;
        }

indexが退社日(n)に達した場合(1からn+1以上)
これ以上仕事ができない.
論理的には、最後の値を入力すると、退社日を超えてしまうので、resの最後の値を除いて報酬を加算し、最後の退社前日に仕事ができるので、idx=nであれば最後の値が加算されます.

        if (idx >= n) {
            int sum = 0;
            for (int i = 0; i < res.size() - 1; i++) {
                sum += res.get(i).money;
            }
            if (idx == n) {
                sum += res.get(res.size() - 1).money;
            }
            answer = Math.max(answer, sum);
            return;
        }

コード#コード#

import java.util.*;


public class Main {

    static int n;
    static List<Counsel> counselList = new ArrayList<>();
    static boolean[] chk;
    static int answer = 0;

    public static class Counsel {
        int time;
        int money;

        public Counsel(int time, int money) {
            this.time = time;
            this.money = money;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            counselList.add(new Counsel(sc.nextInt(), sc.nextInt()));
        }
        chk = new boolean[counselList.size()];

        bf(0, new ArrayList());
        System.out.println(answer);
    }

    public static void bf(int idx, ArrayList<Counsel> res) {

        if (idx >= n) {
            int sum = 0;
            for (int i = 0; i < res.size() - 1; i++) {
                sum += res.get(i).money;
            }
            if (idx == n) {
                sum += res.get(res.size() - 1).money;
            }
            answer = Math.max(answer, sum);
            return;
        }

        for (int i = idx; i < n; i++) {
            if (chk[i]) {
                continue;
            }
            res.add(new Counsel(counselList.get(i).time, counselList.get(i).money));
            chk[i] = true;
            bf(i + counselList.get(i).time, res);
            res.remove(res.size() - 1);
            chk[i] = false;
        }
    }
}