好开心，又搞定一个动规题Order CountProblem Description If we connect 3 numbers with "<" and "=", there are 13 cases: 1) A=B=C 2) A=B<C 3) A<B=C 4) A<B<C 5) A<C<B 6) A=C<B 7) B<A=C 8) B<A<C 9) B<C<A 10) B=C<A 11) C<A=B 12) C<A<B 13) C<B<A If we connect n numbers with "<" and "=", how many cases then? Input The input starts with a positive integer P(0<P<1000) which indicates the number of test cases. Then on the following P lines, each line consists of a positive integer n(1<=n<=50) which indicates the amount of numbers to be connected. Output For each input n, you should output the amount of cases in a single line. Sample Input 213 Sample Output 113Hint Hint Huge input, scanf is recommended. Author weigang Lee MY CODE #include<stdio.h> void mix(int a[],int b[],int c)//大整数乘法 { int i=0,cout=0; while(b[i]!=-1) {   a[i]=b[i]*c+cout;   cout=0;   if(a[i]>=10)   {    cout=a[i]/10;    a[i]=a[i]%10;   }   i++; } while(cout>0) {   a[i++]=cout%10;   cout=cout/10; } a[i]=-1; } void add(int a[],int b[],int c[])//大整数加法 { int i=0,cout=0; while(b[i]!=-1&&c[i]!=-1) {   a[i]=b[i]+c[i]+cout;   cout=0;   if(a[i]>=10)   {    cout=a[i]/10;    a[i]=a[i]%10;   }   i++; } while(b[i]!=-1) {   a[i]=b[i]+cout;   cout=0;   if(a[i]>=10)   {    cout=a[i]/10;    a[i]=a[i]%10;   }   i++; } while(c[i]!=-1) {   a[i]=c[i]+cout;   cout=0;   if(a[i]>=10)   {    cout=a[i]/10;    a[i]=a[i]%10;   }   i++; } if(cout!=0)   a[i]=cout; a[++i]=-1; } void sub(int a[],int b[],int c[])//大整数减法 { int cout=0,i=0,j=0,k=0; while(c[j]!=-1) {   b[i]=b[i]-cout;   cout=0;   if(b[i]<c[j])   {    b[i]=b[i]+10;    cout=1;   }   a[k]=b[i]-c[j];     k++;   j++;   i++; } while(b[i]!=-1) {   if(b[i]<cout)   {    cout=1;    b[i]+=10;   }   a[k]=b[i]-cout;   cout=0;   k++;   i++; } if(a[k-1]==0) a[k-1]=-1; a[k]=-1; k=0; while(a[k]==0) k++; i=0; if(k!=0) {   while(a[k]!=-1)    a[i++]=a[k++];   a[i]=-1; } } int main() { int deng[55][100],f[55][100],temp[100]; int n,m,i,j,k; for(i=0;i<55;i++) {   for(j=0;j<100;j++)   {    deng[i][j]=-1;    f[i][j]=-1;   }   temp[i]=-1; } for(i=55;i<100;i++) temp[i]=-1; f[1][0]=1; f[2][0]=3; deng[0][0]=2; deng[1][0]=1; for(i=3;i<=51;i++) {   k=0;   while(deng[i-2][k]!=-1)   {    f[i][k]=deng[i-2][k];    deng[i-1][k]=deng[i-2][k];    k++;   }   for(j=i-2;j>=2;j--)   {    mix(temp,deng[j-1],i-j);    mix(deng[j],deng[j],i-j);    add(deng[j],temp,deng[j]);    add(f[i],f[i],deng[j]);   }   mix(temp,deng[0],i-1);   mix(deng[1],deng[1],i-1);   add(deng[1],deng[1],temp);   add(f[i],f[i],deng[1]);   mix(deng[0],deng[0],i);   add(f[i],f[i],deng[0]); } scanf("%d",&n); while(n>0) {   n--;   scanf("%d",&m);   i=0;   while(f[m][i]!=-1) i++;   for(i--;i>=0;i--)   printf("%d",f[m][i]);   printf("\n"); } return 0; }

评论