ZOJ 2061 Tickets

DP写的，其过程比较艰难，贴一下代码：
View Code
  1 #include <stdio.h>
  2 #include <string.h>
  3 void add(char s1[],char s2[],char s3[])
  4 {
  5     int len1 = strlen(s1);
  6     int len2 = strlen(s2);
  7     int a[10000];
  8     int k = len1 > len2 ? len1 : len2;
  9     int i,j;
 10     for(i = 0;i <= k;i++)
 11         a[i] = 0;
 12     for(i = len1 - 1,j = k;i >= 0;i--,j--)
 13     {
 14         a[j] = s1[i] - '0';
 15     }
 16     for(i = len2 - 1,j = k;i >= 0;i--,j--)
 17     {
 18         a[j] = a[j] + s2[i] - '0';
 19         a[j - 1] = a[j - 1] + a[j] / 10;
 20         a[j] %= 10;
 21     }
 22     if(a[j] >= 10)
 23     {
 24         a[j - 1] = a[j] / 10;
 25         a[j] %= 10;
 26     }
 27     i = 0;
 28     if(a[0] == 0)
 29         i = 1;
 30     for(j = i;j <= k;j++)
 31         s3[j - i] = a[j] + '0';
 32     s3[j - i] = '\0';
 33 }
 34 void mul(char s1[],char s2[],char s3[])
 35 {
 36     int len1 = strlen(s1);
 37     int len2 = strlen(s2);
 38     int a[10000];
 39     int k = len1 + len2 - 1;
 40     int i,j;
 41     for(i = 0;i <= k;i++)
 42         a[i] = 0;
 43     for(i = len1 - 1;i >= 0;i--)
 44     {
 45         for(j = len2 - 1;j >= 0;j--)
 46         {
 47             a[i + j + 1] += (s1[i] - '0') * (s2[j] - '0');
 48             a[i + j] += a[i + j + 1] / 10;
 49             a[i + j + 1] %= 10;
 50         }
 51     }
 52     if(a[1] >= 10)
 53     {
 54         a[0] = a[1] / 10;
 55         a[1] %= 10;
 56     }
 57     i = 0;
 58     if(a[0] == 0)
 59         i = 1;
 60     for(j = i;j <= k;j++)
 61         s3[j - i] = a[j] + '0';
 62     s3[j- i] = '\0';
 63 }
 64 char dp[101][101][1000];
 65 int main()
 66 {
 67     //开始算阶乘
 68     char fac[101][1000];
 69     char t[101][4];
 70     int i,j;
 71     for(i = 0;i < 100;i++)
 72     {
 73         if(i < 10)
 74         {
 75             t[i][0] = i + '0';
 76             t[i][1] = '\0';
 77         }
 78         if(i >= 10)
 79         {
 80             t[i][0] = i / 10 + '0';
 81             t[i][1] = i % 10 + '0';
 82             t[i][2] = '\0';
 83         }
 84     }
 85     t[100][0] = '1';
 86     t[100][1] = '0';
 87     t[100][2] = '0';
 88     t[100][3] = '\0';
 89     fac[0][0] = '1';
 90     fac[0][1] = '\0';
 91     fac[1][0] = '1';
 92     fac[1][1] = '\0';
 93     for(i = 2;i <= 100;i++)
 94         mul(fac[i - 1],t[i],fac[i]);
 95     //阶乘算完了。。
 96     //开始算DP数组
 97     for(i=0;i<=100;i++)
 98         strcpy(dp[i][0],"1");
 99     for(i=1;i<=100;i++)
100     {
101         for(j=1;j<=i;j++)
102         {
103             if(i==j)
104                 strcpy(dp[i][j],dp[i][j-1]);
105             else
106                 add(dp[i][j-1],dp[i-1][j],dp[i][j]);
107         }
108     }
109     //DP数组算完了。。
110     //对DP数组处理，对分别持有50大洋和100大洋的人数进行全排列
111     for(i = 0;i <= 100;i++)
112     {
113         for(j = 0;j <= 100;j++)
114         {
115             mul(dp[i][j],fac[i],dp[i][j]);
116             mul(dp[i][j],fac[j],dp[i][j]);
117         }
118     }
119     int ncase = 0;
120     while(scanf("%d%d",&i,&j) == 2)
121     {
122         if(i == 0 && j == 0)
123             break;
124         printf("Test #%d:\n",(++ncase));
125         if(i < j)
126             printf("0\n");
127         else
128             printf("%s\n",dp[i][j]);
129     }
130     return 0;
131 }