AOJ 0595 Schedule

またまたJOIのDP問題 自力で解けた

dp[i][j] iは何日目か jは出席する人間のBIT
i日目に出席できる組み合わせは i-1日目の組み合わせに依存するので

dp[i][j] = (jとANDをとって0にならず、 かつ 責任者がいる 一日前のjの和)

としてDP

一日目は必ず Jが出席しないといけないことが抜けててバグバグした

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();
    String m = sc.next();
    int[][] dp = new int[n][1 << 3];
    //000 JOI
    for(int i = 0; i < 1 << 3; i++) {
    
    if(B(Integer.toBinaryString(i)).charAt(JOI(m.charAt(0))) == '1' && B(Integer.toBinaryString(i)).charAt(0) == '1') {
      dp[0][i] = 1;
    }
    }
    
    for(int i = 1; i < n; i++) {
    for(int j = 0; j < 1 << 3; j++) {
      if(B(Integer.toBinaryString(j)).charAt(JOI(m.charAt(i))) == '1') {
      for(int k = 0; k < 1 << 3; k++) {
        if((k & j) != 0) {
        dp[i][j] += dp[i-1][k] % 10007;
        }
      }
      }
    }
    }
    int sum = 0;
    for(int i = 0; i < 1 << 3; i++) {
    sum += dp[n-1][i] % 10007;
    }
    System.out.println(sum % 10007);
    
    
    
  }
  
  static int JOI(char a) {
    if(a == 'J') return 0;
    if(a == 'O') return 1;
    return 2;
  }
  
  static String B(String a) {
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < 3- a.length(); i++) {
    sb.append("0");
    }
    sb.append(a);
    return sb.toString();
  }
}

Schedule | Aizu Online Judge

Source: 13th Japanese Olympiad in Informatics, Preliminary Round , 2013-12-15
http://www.ioi-jp.org/