AOJ 0568 Pasta

なんとか自力で解いたDP問題

dp[i][j] i は 何日目 jはパスタの3日分の履歴 3進数として考えた

import java.util.*;
import java.io.IOException;
import java.math.*;
public class Main {
  static Scanner sc = new Scanner(System.in);

  public static void main(String[] args) {
    int n = sc.nextInt();
    int K = sc.nextInt();
    int[] listA = new int[K];
    int[] listB = new int[K];
    for(int i = 0; i < K; i++) {
    listA[i] = sc.nextInt();
    listB[i] = sc.nextInt();
    }
    
    long[][] dp = new long[n][27];
    IN:for(int i = 0; i < n; i++) {
    if(i == 0) {
      for(int j = 0; j < K; j++) {
      if(1 == listA[j]) {
        int k = listB[j]-1;
        dp[0][k] = 1;
        continue IN;
      }
      }
      for(int j = 0; j < 3; j++) {
      dp[0][j] = 1;
      }
      continue IN;
    }
    if(i == 1) {
      for(int j = 0; j < K; j++) {
      if(2 == listA[j]) {
        int tmp = listB[j]-1;
        for(int k = 0; k < 9; k++) {
        if(k % 3 == tmp) {
          dp[1][k] = dp[0][k/3];
        }
        }
        continue IN;
      }
      }
      for(int j = 0; j < 9; j++) {
      dp[1][j] = dp[0][j/3];
      }
      continue IN;
    }
    for(int j = 0; j < K; j++) {
      if(i+1 == listA[j]) {
      for(int k = 0; k < 27; k++) {
        if(k % 3 == listB[j]-1 && !(k%3 == (k%9)/3 && (k%9)/3 == k/9)) {
        dp[i][k] += dp[i-1][(k/9)*3 + (k%9)/3] + dp[i-1][9 + (k/9)*3 + (k%9)/3] + dp[i-1][18 + (k/9)*3 + (k%9)/3];
        dp[i][k] %= 10000;
        }
      }
      continue IN;
      }
    }
    for(int k = 0; k < 27; k++) {
    if(!((k%3) == (k%9)/3 && (k%9)/3 == k/9)) {
      dp[i][k] += dp[i-1][(k/9)*3 + (k%9)/3] + dp[i-1][9 + (k/9)*3 + (k%9)/3] + dp[i-1][18 + (k/9)*3 + (k%9)/3];
      dp[i][k] %= 10000;
    }
    }
    }
    int sum = 0;
    for(int i = 0; i < 27; i++) {
    sum += dp[n-1][i] % 10000;
    sum %= 10000;
    }
    System.out.println(sum);
  }
}