ABC080 C (DPS)

問題

• DPS問題
• 再帰呼び出しの練習になる
• 例外処理も含んでいる
• staticなグローバル変数の使用練習にもなる
• 難しいけど練習になる問題だった
• 今回は他人のコードの力を借りずに解説放送を頼りに自分で書いてみた

自分のコード

public class Main {
// 以下のメソッドでも使いたい変数なのでグローバル変数として定義しておく。
// 配列は要素数がまだ入力されていないので初期化はしない。
    static int open[] = new int[10];
    static int ans = Integer.MIN_VALUE;
    static int n;
    static int f[][];
    static Scanner sc;

    static int p[][];
    static boolean first = true;

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        n = sc.nextInt();
        f = new int[n][10];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                f[i][j] = sc.nextInt();
            }
        }
        p = new int[n][11];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 11; j++) {
                p[i][j] = sc.nextInt();
            }
        }
        // 入力終了
        DFS(0);
        System.out.println(ans);
    }

DFS関数

    public static void DFS(int pos) {
        if (pos >= 10) {
            return;
        }
        open[pos] = 0;

        func();

        DFS(pos + 1);
        open[pos] = 1;
        func();
        DFS(pos + 1);

    }

初めは初期値としてopenには１０個の0が格納されている。posの位置の値を0と1変化させてもう一度DFSをposの値を変化させて計算する。

func 関数

    // ansの書き換え
    public static void func() {
        int opencnt = 0;
        for (int i = 0; i < 10; i++) {
            if (open[i] == 0) {
                opencnt++;
            }
        }
        if (opencnt == 10) {
            return;
        }
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            int cnt = 0;
            for (int j = 0; j < 10; j++) {
                if (open[j] == 0) {
                    continue;
                } else {
                    if (f[i][j] == 1) {
                        cnt++;
                    }
                }
            }
            tmp += p[i][cnt];
        }
        ans = Math.max(ans, tmp);
    }
}

この関数ではDFSで変化させた後のopen[]に対して実際にいくらの利益が出るかを計算している。 計算の結果が今までより大きかったら更新する。
- 今回条件では必ず一回は回転しなくてはならないのでopenが全て0の場合は処理を行わないよにしなくてはならなかった。 ---- 追記

DPSのイメージ。対象の場所に関して0 1 を変えそれぞれについて再帰呼び出しする。