#华为笔试#9.14笔试第1题

public class Exer1Preview {
    /*
        题目：有一个人过桥，桥上面有 n 块木板，有些木板是断的，如果
        走到了断的木板上，则会损失一条生命值，这个人的初始生命值条数
        是 m 条生命。每次可以选择 不跳(从当前位置走到下一块木板)，
                               或跳一格(从当前位置跳过一块木板)，
                               或跳两格(从当前位置跳过两块木板)
        要求走到终点时，生命值至少有1条。
        求顺利过桥的方案数？
        输入：m —— 代表初始生命值条数
             n —— 代表桥的长度，即桥上总共有多少块木板
             k —— 代表桥上有多少块木板是断裂的
             k个整数，分别代表断裂木板的编号，第一块木板的编号是 1
        输出：顺利过桥的方案数
     */
    public static void main(String[] args) {

        // 处理输入
        Scanner scanner = new Scanner(System.in);
        int mOfLifes = scanner.nextInt();
        int nOfBridges = scanner.nextInt();
        int kOfBreakages = scanner.nextInt();
        // 起点对应的位置是 0 ，终点对应的位置是 nOfBridges + 1
        boolean[] sequenceOfBridges = new boolean[nOfBridges + 2];
        int sequence = 0;  // 代表断裂木板的编号
        for(int i = 0;i < kOfBreakages;i++){
            sequence = scanner.nextInt();
            // 若第 i 块木板断裂，则 sequenceOfBridges[i]为true，否则为false
            sequenceOfBridges[sequence] = true;
        }

        // 中间过程
        /*
            算法思想：
                动态规划，dp[i][j]:从起点走到第i块木板剩余j条命的 走法方案数
                初始状态:
                    dp[0][mOfLifes] = 1, (从起点走到起点，剩余mOfLifes条命的走法只有1种)
                    dp[0][j] = 0 ,其中j < mOfLifes (从起点走到起点，剩余j条命的走法是0种)
                状态转移方程：
                    dp[i][j+lose] = dp[i-1][j] + dp[i-2][j] + dp[i-3][j]
                分析：若第i块木板断裂，则lose的值为-1，若第i块木板未断裂，则lose的值为0
                若想求出从起点走到第i块木板有多少种走法，取决于：
                    从起点走到第i-1块木板的走法，再走一步
                    从起点走到第i-2块木板的走法，再跳过一格
                    从起点走到第i-3块木板的走法，再跳过两格
                因为第i块木板有可能是断裂的，所以走到第i块时，剩下的生命值是j+lose
         */
        int[][] dp = new int[nOfBridges+2][mOfLifes+1];
        dp[0][mOfLifes] = 1;
        int lose = 0;
        for(int i = 1;i <= nOfBridges+1;i++){
            lose = sequenceOfBridges[i] ? -1 : 0;
            // 走一步
            if(i-1 >= 0){
                for(int j = 1;j <= mOfLifes;j++){
                    dp[i][j+lose] = dp[i][j+lose] + dp[i-1][j];
                }
            }

            // 跳一格
            if(i-2 >= 0){
                for(int j = 1;j <= mOfLifes;j++){
                    dp[i][j+lose] = dp[i][j+lose] + dp[i-1][j];
                }
            }

            // 跳两格
            if(i-3 >= 0){
                for(int j = 1;j <= mOfLifes;j++){
                    dp[i][j+lose] = dp[i][j+lose] + dp[i-1][j];
                }
            }
        }

        // 处理输出
        int solutions = 0;
        for(int i = 1;i < mOfLifes;i++){
            solutions = solutions + dp[nOfBridges+1][i];
        }
        System.out.println(solutions);
    }
}