bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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


posted on 2008-01-29 21:35 bon 阅读(243) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator