PKU 1775 Sum of Factorials
http://poj.org/problem?id=1775
0以上100万以下の数が入力されるので、いくつかの異なる数の階乗の和で表されるものかどうかを判定する。
せいぜい9!までしか調べなくて良いので、全探索しようとしたらTLEしました。
なので、事前計算しました。
0が入力に含まれているのに気づかずなぜか1OLE。
bool ans[1000001]; main(){ int f=1; ans[0]=1; rep(i,10){ if(i)f*=i; for(int j=1000000-f;j>=0;j--){ if(ans[j])ans[j+f]=true; } } ans[0]=false; int n; while(cin>>n,n>=0)cout<<(ans[n]?"YES":"NO")<<endl; }