TopCoder SRM 662 Div1 Medium: ExactTree
コード
import java.util.Arrays; public class ExactTree { private final int INF = 1 << 25; public int getTree(int N, int MOD, int R) { // dp[n][r]:= 頂点数nの木で、あまりがrになる時のコスト int[][] dp = new int[N + 1][MOD]; for (int i = 0; i <= N; i++) { Arrays.fill(dp[i], INF); } dp[1][0] = 0; for (int n = 2; n <= N; n++) { for (int i = 1; i < n; i++) { int j = n - i; for (int r1 = 0; r1 < MOD; r1++) { for (int r2 = 0; r2 < MOD; r2++) { // 最初から頂点をNにするつもりで増加量を計算すると手間が減る int cost = dp[i][r1] + dp[j][r2] + i * (N - i); int r = cost % MOD; dp[n][r] = Math.min(dp[n][r], cost); } } } } if (dp[N][R] >= INF) { return -1; } return dp[N][R]; } }