Indeedなう A日程 C: Optimal Recommendations

問題

C: Optimal Recommendations - Indeedなう（オープンコンテスト） | AtCoder

解法

dp[i][j][k]:= 能力i, j, k の人が行ける最高の報酬の会社

として、

dp[i][j][k + 1] = Math.max(dp[i][j][k + 1], dp[i][j][k]);
dp[i][j + 1][k] = Math.max(dp[i][j + 1][k], dp[i][j][k]);
dp[i + 1][j][k] = Math.max(dp[i + 1][j][k], dp[i][j][k]);
dp[i + 1][j + 1][k] = Math.max(dp[i + 1][j + 1][k], dp[i][j][k]);
dp[i + 1][j][k + 1] = Math.max(dp[i + 1][j][k + 1], dp[i][j][k]);
dp[i][j + 1][k + 1] = Math.max(dp[i][j + 1][k + 1], dp[i][j][k]);
dp[i + 1][j + 1][k + 1] = Math.max(dp[i + 1][j + 1][k + 1], dp[i][j][k]);

のように更新してやれば良い（もっときれいに書けると思う）。i, j, kともに100以下なのでO(1000000)で計算できる。

コード

import java.io.IOException;

public class Main {
	public static void main(String[] args) {
		int N = nextInt();
		int M = nextInt();
		int[][][] dp = new int[102][102][102];
		for (int i = 0; i < N; i++) {
			int x = nextInt();
			int y = nextInt();
			int z = nextInt();
			int w = nextInt();
			dp[x][y][z] = Math.max(dp[x][y][z], w);
		}
		for (int i = 0; i <= 100; i++) {
			for (int j = 0; j <= 100; j++) {
				for (int k = 0; k <= 100; k++) {
					dp[i][j][k + 1] = Math.max(dp[i][j][k + 1], dp[i][j][k]);
					dp[i][j + 1][k] = Math.max(dp[i][j + 1][k], dp[i][j][k]);
					dp[i + 1][j][k] = Math.max(dp[i + 1][j][k], dp[i][j][k]);
					dp[i + 1][j + 1][k] = Math.max(dp[i + 1][j + 1][k], dp[i][j][k]);
					dp[i + 1][j][k + 1] = Math.max(dp[i + 1][j][k + 1], dp[i][j][k]);
					dp[i][j + 1][k + 1] = Math.max(dp[i][j + 1][k + 1], dp[i][j][k]);
					dp[i + 1][j + 1][k + 1] = Math.max(dp[i + 1][j + 1][k + 1], dp[i][j][k]);
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			int x = nextInt();
			int y = nextInt();
			int z = nextInt();
			sb.append(dp[x][y][z]);
			sb.append('\n');
		}
		System.out.print(sb.toString());
	}

	static int nextInt() {
		int c;
		try {
			c = System.in.read();
			while (c != '-' && (c < '0' || c > '9'))
				c = System.in.read();
			if (c == '-')
				return -nextInt();
			int res = 0;
			while (c >= '0' && c <= '9') {
				res = res * 10 + c - '0';
				c = System.in.read();
			}
			return res;
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return -1;
	}
}