首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。