hdu 1566 奇怪的公式

#include
#include
short f[1002][1002];
short dp[1002][102];
short s[1002][5];
//高精度乘法
void mult(short *a,short *b,short *c)
{//c=a*b;
  int i,j,m,n,k;
  if(a[0]==1&&a[1]==0||b[0]==1&&b[1]==0) 
  {c[0]=1;c[1]=0;return;}
  m=a[0];n=b[0];
  k=n+m-1;
  for(i=0;i<=k;i++)c[i]=0;
  for(i=1;i<=m;i++) {
   if(a[i])for(j=1;j<=n;j++)if(b[j])c[i+j-1]+=a[i]*b[j];
  }
  for(i=k;i>=1;i--)if(c[i]>9){  c[i-1]+=c[i]/10;c[i]%=10;}
  if(c[0]>0)
  {k++; for(i=k;i>=1;i--)c[i]=c[i-1];   }c[0]=k;
}

void dectoB(int sum,int b,short *S)
{ //将数sum用数组表示(b进制)
  int i,j,k=0,t,d[20];
  while(sum>0) {  d[++k]=sum%b; sum/=b;  } 
  S[0]=k;
  for(i=1,j=k;i<=k;i++,j--) {S[i]=d[j];}
}  

void copy(short *a,short *b)
{
 int i;
 for(i=0;i<=b[0];i++)
  a[i]=b[i];
}

//a>b return 1  a<=b return 0
int big(short *a,short *b)
{
 int i;
 if(a[0]>b[0]) return 1;
 if(a[0] for(i=1;i<=a[0];i++)
 {
  if(a[i]  if(a[i]>b[i]) return 1;
 }
 return 0;
}

int main()
{
    int i,j,pos,n,k;
 short temp[105];
/*
思想：dp
dp[n]=max(dp[i]*(n-i))     1<=i同时为了保证没重复  f[][]做标记
*/
  //初始化处理
  for(i=1;i<=1000;i++) dectoB(i,10,s[i]);
  memset(f,0,sizeof(f));
  dp[1][0]=1;dp[1][1]=1;f[1][1]=1;f[1][0]=1;
  dp[2][0]=1;dp[2][1]=2;f[2][2]=1;f[2][0]=1;
  dp[3][0]=1;dp[3][1]=3;f[3][3]=1;f[3][0]=1;
  for(i=4;i<=1000;i++)
  {  
    pos=i;
    for(j=1;j    //if(f[j][i-j]==0&&dp[j]*(i-j)>dp[i])
 //{dp[i]=dp[j]*(i-j);pos=j;}
    if(f[j][i-j]==0)
 {
  mult(dp[j],s[i-j],temp);

  if(big(temp,dp[i]))
  {copy(dp[i],temp);pos=j;}
 }

 //f[i][0]=0;
    for(j=1,k=0;j<=1000&&k<=f[pos][0];j++)
 {
  f[i][j]=f[pos][j];
     if(f[i][j])k++;
 }
 f[i][i-pos]=1;
 f[i][0]=f[pos][0]+1;

  //if(i<20) printf("%d\n",f[i][0]);
  }   
 
  while(scanf("%d",&n)!=EOF)
  {
  if(n==3){printf("2 1 2\n2\n");continue;}
  printf("%d",f[n][0]);
  for(i=1,j=0;i<=1000&&j<=f[n][0];i++)
   if(f[n][i]) {printf(" %d",i);j++;}
  printf("\n");
  //printf("%I64d\n",dp[n]);                         
  for(i=1;i<=dp[n][0];i++) printf("%d",dp[n][i]);
  printf("\n");
  }
}

/*
10
3 2 3 5
30
20
5 2 3 4 5 6
720
30
6 2 3 4 6 7 8
8064
40
7 2 3 5 6 7 8 9
90720
50
8 2 3 5 6 7 8 9 10
907200
60
9 2 3 4 6 7 8 9 10 11
7983360
70
10 2 3 4 5 6 8 9 10 11 12
68428800
80
11 2 3 4 5 6 7 8 9 11 12 13
622702080
90
12 2 3 4 5 6 7 8 9 10 11 12 13
6227020800
100
12 2 3 5 6 7 8 9 10 11 12 13 14
21794572800
150
15 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
177843714048000
200
18 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 18 19 20
270322445352960000
300
23 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25
646300418472124416000000
400
26 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
60977668922342772100300800000
500
30 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 29 30 3
1 32
9745586553099760376563630080000000
600
33 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 30 3
1 32 33 34 35
356315447116763618264367287500800000000
700
35 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37
6881876545613172523157989790790451200000000
800
38 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 20 21 22 23 24 25 26 27 28 29 30 3
1 32 33 34 35 36 37 38 39 40
42942909644626196544505856294532415488000000000
900
40 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42
702503058876439949271571303122255784968192000000000
1000
43 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3
0 31 32 33 35 36 37 38 39 40 41 42 43 44 45
3518300613690593957704798867519344560717168640000000000

*/