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;
}
|