pku1775本題的大意是給定一個數n，判斷n能否表示成若干個數的階乘的形式。
 // pku 1775 給出一個數n,1<=n<=1000000，問能否表示成為一些階乘數的和，如9=1!+2!+3!
#include <iostream>
using namespace std;
//0到9的factorial，從第1個單元開始
  long data[11]= {1,1,2,6,24,120,720,5040,40320,362880};
int comb[12]={1,10,45,120,210,252,210,120,45,10,1};
long a[10]; //存儲組合
int flag; //標識是否存在這樣的和
int cnt; //標識要去多少個factorial
long target; //要求的數
long d[11][300][2]; // d[i][j][0]表示i個數的和，組成這個和值的最大數在data數組中的下標是d[i][j][1]
void dp()
{// 遞推算出所有可能的值
 int i,j,k,l;
// 只有一個數的情況
  for(i=0;i<=9;i++) {d[1][i][0]=data[i];d[1][i][1]=i;}
// 從2個數到10個數的組合
for(i=2;i<=10;i++)
{
for(k=0,j=0;j<comb[i-1];j++)
{
int maxi=d[i-1][j][1];
int sum=d[i-1][j][0];
for(l=maxi+1;l<=9;l++)
{
d[i][k][0]=sum+data[l];
d[i][k++][1]=l;
 }
}
}
/**//*
for(i=1;i<=10;i++)
{
for(j=0;j<comb[i];j++) printf("%d ",d[i][j][0]);
printf("\n");
}
*/
 }
int main()
{
cnt=3;
dp();
while(scanf("%ld",&target) && target>=0)
{
if(target==0) printf("NO\n");
else
{
int flag=0;
for(int i=1;i<=10;i++)
{
for(int j=0;j<comb[i];j++)
{
if(d[i][j][0]==target) {flag=1;break;}
}
}
if(flag==1) printf("YES\n");
else printf("NO\n");
}
}
return 1;
}
|