拼多多笔试2019.9.25算法笔试第四题 动态规划

package pdd;

import java.util.Scanner;

//public class Main {
public class game{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextInt()){
            int T = sc.nextInt();
            for(int i=0; i<T; i++){
                int n = sc.nextInt();
                int m = sc.nextInt();


                int[][] film = new int [m][2];

                int [][] happy = new int[n][5];

                for(int j=0; j<m; j++)
                    film[j][0] = sc.nextInt();

                for(int j=0; j<m; j++)
                    film[j][1] = sc.nextInt();

                int z = 1;

                if(m>0 && film[0][0]==1){
                    happy[0][film[0][1]] = 1;
                    z += 1;
                }else{
                    for(int j=1; j<=4; j++)
                        happy[0][j] = 1;
                }

                for(int k=1; k<n; k++){
                    for(int j=1; j<=4; j++){
                        for(int l=1; l<=4; l++){
                            if(l != j){
                                happy[k][j] += happy[k-1][l];
                                happy[k][j] %= (Math.pow(10, 9)+7);
                            }
                        }

                    }
                    if(z <= m){
                        if(k+1 == film[z-1][0]){
                            for(int y=1; y<=4; y++){
                                if(y != film[z-1][1])
                                    happy[k][y] = 0;
                            }
                            z++;
                        }
                    }
                }
                long sum = 0;
                for(int j=1; j<=4; j++)
                    sum += happy[n-1][j];
                sum %= (Math.pow(10, 9)+7);

                System.out.println(sum);

            }

        }
    }

}