問題を解く

トップレベルdp練習兼トップレベルで説明しました.
最大値と最小値が要求されるため,2つのdp配列を記述し,最大値を求める関数,最小値を求める関数を求めた.
d配列は最大値を格納する配列であり、d 2配列は最小値を格納する配列である.
最大値を格納する必要があるため、それぞれ−1、987654321に初期化される.
ベースインスタンスi=n−1の場合、arr[i][j]が返される.
また、現在の最大値または最小値=現在の配列の値+次の行で得られる点数の最大値または最小値です.
d[0][0]、d[0][1]、およびd[0][2]から最大値を得ることができる.
d 2[0][0]、d 2[0][1]、d[0][2]から最小値を得ることができる.

質問リンク

boj/2096

ソースコード

PS/2096 .java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[][] d;
    static int[][] d2;
    static int[][] arr;

    static int solve(int i, int j) {
        if (d[i][j] != -1)
            return d[i][j];
        if (i == n - 1)
            return arr[i][j];
        d[i][j] = 0;
        if (j == 0)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), solve(i + 1, 1));
        else if (j == 1)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 0), Math.max(solve(i + 1, 1), solve(i + 1, 2)));
        else if (j == 2)
            d[i][j] = arr[i][j] + Math.max(solve(i + 1, 1), solve(i + 1, 2));
        return d[i][j];
    }

    static int solve2(int i, int j) {
        if (d2[i][j] != 987654321)
            return d2[i][j];
        if (i == n - 1)
            return arr[i][j];
        d2[i][j] = 0;
        if (j == 0)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), solve2(i + 1, 1));
        else if (j == 1)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 0), Math.min(solve2(i + 1, 1), solve2(i + 1, 2)));
        else if (j == 2)
            d2[i][j] = arr[i][j] + Math.min(solve2(i + 1, 1), solve2(i + 1, 2));
        return d2[i][j];
    }

    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        d = new int[n][3];
        d2 = new int[n][3];
        arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            Arrays.fill(d[i], -1);
            Arrays.fill(d2[i], 987654321);
        }
        int max = Math.max(Math.max(solve(0, 0), solve(0, 1)), solve(0, 2));
        int min = Math.min(Math.min(solve2(0, 0), solve2(0, 1)), solve2(0, 2));
        System.out.println(max + " " + min);


    }
}