题目的意思是给你一个数n,然后有n个A,n个B,n个C,由这些组成一个长为3n的字符串,并且对于这个字符串的每个前缀,Num(A)>=Num(B)>=Num(C)。

由于数很大,所以用java写了。递推式是:

dp[i][j][[k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1]。

dp[i][j][k]代表使用了i个A,j个B,k个C。


代码:

StatusAccepted
Time327ms
Memory24288kB
Length1136
LangJava
import java.math.BigInteger;
import java.util.Scanner;
/**
 * Created by chen on 2017/4/21 0021.
 */
public class Main{
    static final int maxn = 65;
    static BigInteger dp[][][] = new BigInteger[maxn][maxn][maxn];
    private static void Inital(){
        for(int i=0;i<maxn;i++)for(int j=0;j<maxn;j++)for(int k=0;k<maxn;k++)dp[i][j][k]=BigInteger.ZERO;
        dp[1][0][0] = BigInteger.ONE;
        dp[1][1][0] = BigInteger.ONE;
        dp[1][1][1] = BigInteger.ONE;
        for(int i=2;i<=60;i++){
            for(int j=0;j<=60;j++){
                for(int k=0;k<=60;k++){
                    if(i-1>=j)dp[i][j][k]=dp[i][j][k].add(dp[i-1][j][k]);
                    if(j-1>=k)dp[i][j][k]=dp[i][j][k].add(dp[i][j-1][k]);
                    if(k-1>=0)dp[i][j][k]=dp[i][j][k].add(dp[i][j][k-1]);
                }
            }
        }
    }
    public static void main(String args[]){
        Inital();
        Scanner cin = new Scanner(System.in);
        int n;
        while (cin.hasNext()){
            n = cin.nextInt();
            System.out.println(dp[n][n][n]);
            System.out.println();
        }
    }
}