AOJ0568 Pasta
問題リンク Pasta
- 解法
DPもといメモ化探索です。
dp[v][s][c]: V日目からパスタSを厳密にC日間続けたときのV〜N日目の予定の組み合わせ数
という表を埋めることで解けます。
各パスタを1日続ける場合、2日続ける場合から予定が始まるので、最終的な答えは
(dp[1][0][1]+dp[1][0][2] + dp[1][1][1]+dp[1][1][2] + dp[1][2][1]+dp[1][2][2])%10000
になります。
- ソース
import java.util.Arrays; import java.util.Scanner; //Pasta public class AOJ0568 { int n, k, MOD = 10000; int[] a; int[][][] dp; int get(int v, int s, int c){ if(a[v]!=-1&&a[v]!=s)return 0; if(v==n)return c==1?1:0; if(dp[v][s][c]!=-1)return dp[v][s][c]; int res = 0; if(c==1){ for(int j=0;j<3;j++){ if(s==j)continue; res = (res+get(v+1, j, 1)+get(v+1, j, 2))%MOD; } } else res = get(v+1, s, 1); return dp[v][s][c] = res; } void run(){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); k = sc.nextInt(); a = new int[n+1]; Arrays.fill(a, -1); while(k--!=0)a[sc.nextInt()]=sc.nextInt()-1; dp = new int[n+1][3][3]; for(int[][]b:dp)for(int[]c:b)Arrays.fill(c, -1); int res = 0; for(int j=0;j<3;j++)for(int c=1;c<3;c++)res+=get(1, j, c); System.out.println(res%MOD); } public static void main(String[] args) { new AOJ0568().run(); } }