火车调度的可行性满足卡特兰数,所以可以直接用卡特兰数的递推公式解题。由于题目N的范围是1~100,所以需要使用大数计算。卡特兰数的递推公式为:
F(n)=F(n-1)*(4n-2)/(n+1)
#include <stdio.h> #define DEPTH 10000; int a[101][16]; void ktl() { a[1][1]=1; a[1][0]=1; for(int i=2;i<=100;++i) { int left=0,assist,j; for(j=1;j<=a[i-1][0]; ++j ) { assist=a[i-1][j]*(4*i-2)+left; left=assist/DEPTH; a[i][j]=assist%DEPTH; } a[i][0]=j; if(left) a[i][j]=left; else a[i][0]--; assist=0; for(j=a[i][0];j>=1;--j ) { assist=a[i][j]+assist*DEPTH; a[i][j]=assist/( i+1 ); assist=assist%(i+1); } while(a[i][a[i][0]]==0) a[i][0]--; } } int main() { //freopen("Train Problem II.txt","r",stdin); ktl(); int n; while(scanf("%d",&n )!=EOF) { printf("%d",a[n][a[n][0]]); for( int j=a[n][0]-1;j>0;--j) { printf( "%04d",a[n][j]); } printf("\n"); } }