pku1775本题的大意是给定一个数n,判断n能否表示成若干个数的阶乘的形式。
// pku 1775 给出一个数n,1<=n<=1000000,问能否表示成为一些阶乘数的和,如9=1!+2!+3!
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
//0到9的factorial,从第1个单元开始
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) long data[11]= {1,1,2,6,24,120,720,5040,40320,362880};
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) 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]
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void dp()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {// 递推算出所有可能的值
int i,j,k,l;
// 只有一个数的情况
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) 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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(k=0,j=0;j<comb[i-1];j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int maxi=d[i-1][j][1];
int sum=d[i-1][j][0];
for(l=maxi+1;l<=9;l++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
d[i][k][0]=sum+data[l];
d[i][k++][1]=l;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) /**//*
for(i=1;i<=10;i++)
{
for(j=0;j<comb[i];j++) printf("%d ",d[i][j][0]);
printf("\n");
}
*/
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
cnt=3;
dp();
while(scanf("%ld",&target) && target>=0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(target==0) printf("NO\n");
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int flag=0;
for(int i=1;i<=10;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(int j=0;j<comb[i];j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(d[i][j][0]==target) {flag=1;break;}
}
}
if(flag==1) printf("YES\n");
else printf("NO\n");
}
}
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|