BOJ 5721あめ拾い大会

16306 ワード
テキストリンク

質問する


問題の要約は難しいですが、リンクを参照してください.

に近づく

  • 本当に驚くべき事実は、行と列が互いに影響しないことです.どういう意味か知るために考えてみた一次元配列があることを想像してみてください.砂糖拾いの試合のルールのように、キャンディをあげると、両側のキャンディがなくなります.この場合、最大の結果を得るためにはどうすればいいのでしょうか.
  • d[N]d[N]d[N]d[N]は、N番目のインデックスに対する最大結果として定義される.
  • であれば、N番目のインデックスのキャンディを2つに分けて点火式を確立することができます.
    d[N]=MAX(d[N−2]+a[N],d[N−1])d[N] = MAX(d[N-2]+a[N], d[N-1])d[N]=MAX(d[N−2]+a[N],d[N−1])
  • から、考え方をさらに拡張し、問題に適用します.各行について、次の手順3に従って、行で得られる最大キャンディ値を取得します.次に、各行の最大値を取得します.
  • ビットの結果が得られた場合,同様のプロセスを繰り返す点火式を再確立することができる.dではなくeを使用して、各行の最大値を区別します.
    e[N]=MAX(e[N−2]+e[N],e[N−1])e[N] = MAX(e[N-2]+e[N], e[N-1])e[N]=MAX(e[N−2]+e[N],e[N−1])

    • コード#コード#

    import java.io.*;
import java.util.*;

class baek__5721 {
    static int[][] map;
    static int[][] d;
    static int[][] d2;

    static int go(int n, int m) {// 열에서 큰거
        if (m < 0)
            return 0;

        if (d[n][m] != -1)
            return d[n][m];

        d[n][m] = Math.max(go(n, m - 2) + map[n][m], go(n, m - 1));

        return d[n][m];
    }

    static int go2(int n, int m) {
        if (n < 0)
            return 0;

        if (d2[n][m] != -1)
            return d2[n][m];

        d2[n][m] = Math.max(go2(n - 2, m) + go(n, m), go2(n - 1, m));

        return d2[n][m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringBuilder sb = new StringBuilder();
        while (true) {
            String[] temp = br.readLine().split(" ");
            int r = Integer.parseInt(temp[0]);
            int c = Integer.parseInt(temp[1]);
            if (r == 0 && c == 0)
                break;

            map = new int[r][c];
            d = new int[r][c];
            d2 = new int[r][c];

            for (int i = 0; i < r; i++) {
                temp = br.readLine().split(" ");
                for (int j = 0; j < c; j++) {
                    map[i][j] = Integer.parseInt(temp[j]);
                    d[i][j] = -1;
                    d2[i][j] = -1;
                }
            }

            sb.append(go2(r - 1, c - 1) + "\n");
        }
        System.out.print(sb);
    }
}
    HTML TAGS
    quartzの使用例