TimusOJ - 2018. The Debut Album

Question

题目

和上一个题目很像，给你三个数 N、A、B ，要你将 N 个数（只包含 1、2 ) 排列，其中 1 不能连续有 A 个， 2 不能连续有 B 个，问你有多少中摆放方法。

解析

这个题目不能用第一个题目的第一种方法，因为这样内存消耗很大。

MLE 代码:

import java.io.*;
import java.util.*;

public class Main{ 

    static int N, A, B;
    final static int mod = 1000000000 + 7;
    static int[][][] dp;

    static int recur(int n, int a, int b){
        if(n == N)
            return 1;
        if(dp[n][a][b] != -1)
            return dp[n][a][b];
        int res = 0;
        if(a < A)
            res += recur(n+1, a+1, 0);
        if(b < B)
            res += recur(n+1, 0, b+1);
        return dp[n][a][b] = res % mod;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        N = cin.nextInt();
        A = cin.nextInt();
        B = cin.nextInt();
        dp = new int[N+1][A+1][B+1];
        for(int i = 0; i <= N; i++){ 
            for(int j = 0; j <= A; j++){ 
                for(int k = 0; k <= B; k++)
                    dp[i][j][k] = -1;
            }
        }
        out.println((recur(0, 0, 0) + mod)%mod);
    }
}

同样也是第二种方法的思路，这里给出递归和递推的代码:

import java.io.*;
import java.util.*;

public class Main{ 

    static int N, A, B;
    final static int mod = 1000000000 + 7;
    static int[][] dp;

    static int recur(int n, int cate){
        if(n == 0)
            return 1;
        if(dp[n][cate] != -1)
            return dp[n][cate];
        int res = 0;
        if(cate == 1){
            for(int i = 1; n - i >= 0 && i <= Math.min(N, A); i++)
                res = (res + recur(n - i, 2)) % mod;
        }else { // cate == 2 
            for(int i = 1; n - i >= 0 && i <= Math.min(N, B); i++)
                res = (res + recur(n - i, 1)) % mod;
        }
        return dp[n][cate] = res % mod;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        N = cin.nextInt();
        A = cin.nextInt();
        B = cin.nextInt();
        dp = new int[N+1][3];
        for(int i = 0; i <= N; i++){ 
            dp[i][1] = -1;
            dp[i][2] = -1;
        }
        out.println( (recur(N, 1) + recur(N, 2) )%mod);
    }
}

import java.io.*;
import java.util.*;

public class Main{ 

    final static int mod = 1000000000 + 7;

    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        PrintStream out = System.out;
        int N = cin.nextInt();
        int A = cin.nextInt();
        int B = cin.nextInt();
        int[][] dp = new int[N+1][3];
        dp[0][1] = 1; dp[0][2] = 1;
        for(int cur = 1; cur <= N; cur++){ 
            for(int i = 1; cur-i >= 0 && i <= Math.min(N, A); i++)
                dp[cur][1] = (dp[cur][1] + dp[cur-i][2]) % mod;
            for(int i = 1; cur-i >= 0 && i <= Math.min(N, B); i++)
                dp[cur][2] = (dp[cur][2] + dp[cur-i][1]) % mod;
        }
        out.println( (dp[N][1] + dp[N][2]) % mod);
    }
}

题目链接

http://acm.timus.ru/problem.aspx?space=1&num=2018