首页 > 代码库 > zoj 2711 - Regular Words

zoj 2711 - Regular Words

题目:求由A。B。C构成的有序传中长度为n。且每一个B前面的A的个数不少于当前B,每一个C前面的B的个数不少于当前C的个数。

分析:dp,求排列组合数。

           考虑二维的状况:

                  假设 A>=B 则在 F(A-1。B)后面放上A,在F(A。B-1)后面放上B。

                  F(A。B)= F(A,B-1)+ F(A-1,B) { A > B }。

                  当 A = B 时 也满足  F(A,B)= F(A,B-1)+ F(A-1。B)= F(A。B-1)+ 0;

                  所以有: F(A。B)= F(A,B-1)+ F(A-1,B) { A >= B }。

           考虑三维的状况:

                  F(A,B,C)= F(A-1,B,C)+ F(A,B-1,C-1)+ F(A,B。C-1) {A >= B >= C}。

说明:(2011-09-19 01:32)。

#include <stdio.h>
#include <string.h>

char ABC[ 61 ][ 61 ][ 61 ][ 82 ];

int main()
{
    memset( ABC, 0, sizeof( ABC ) );
    for ( int A = 1 ; A <= 60 ; ++ A )
        ABC[ A ][ 0 ][ 0 ][ 0 ] = 1;
    
    for ( int A = 1 ; A <= 60 ; ++ A )
    for ( int B = 1 ; B <= 60 ; ++ B )
        if ( A >= B ) 
            for ( int k = 0 ; k <= 80 ; ++ k ) {
                ABC[ A ][ B ][ 0 ][ k ] += ABC[ A-1 ][ B ][ 0 ][ k ] + ABC[ A ][ B-1 ][ 0 ][ k ];
                if ( ABC[ A ][ B ][ 0 ][ k ] > 9 ) {
                     ABC[ A ][ B ][ 0 ][ k+1 ] += ABC[ A ][ B ][ 0 ][ k ]/10;
                     ABC[ A ][ B ][ 0 ][  k  ] %= 10;
                }
            }
    
    for ( int A = 1 ; A <= 60 ; ++ A )
    for ( int B = 1 ; B <= 60 ; ++ B )
    for ( int C = 1 ; C <= 60 ; ++ C )
        if ( A >= B && B >= C ) 
            for ( int k = 0 ; k <= 80 ; ++ k ) {
                ABC[ A ][ B ][ C ][ k ] += ABC[ A-1 ][ B ][ C ][ k ] + ABC[ A ][ B-1 ][ C ][ k ] + ABC[ A ][ B ][ C-1 ][ k ];
                if ( ABC[ A ][ B ][ C ][ k ] > 9 ) {
                     ABC[ A ][ B ][ C ][ k+1 ] += ABC[ A ][ B ][ C ][ k ]/10;
                     ABC[ A ][ B ][ C ][  k  ] %= 10; 
                }
            }
    
    int n;
    while ( scanf("%d",&n) != EOF ) {
        int start = 80;
        while ( !ABC[ n ][ n ][ n ][ start ] && start > 0 ) -- start;
        while ( start >= 0 )
            printf("%d",ABC[ n ][ n ][ n ][ start -- ]);
        printf("\n\n");
    }
    return 0;
}

zoj 2711 - Regular Words