PKU 1775-Sum of Factorials
問題概要
Nが異なる一つ以上の数値の階乗の和で表せるかどうか調べろ。N<0の時終了とする。
解法
動的計画法によってあらかじめ調べておく。
DP[n][k]はNを数をk未満の数の階乗の和で表せることを意味する。
実装(C++)
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> using namespace std; int fact[10]; char dp[1000001][11]; int main(){ fact[0]=1; for(int i=1;i<10;i++){ fact[i]=fact[i-1]*i; } dp[0][0]=1; for(int k=0;k<10;k++){ for(int i=0;i<1000001;i++){ if(dp[i][k]&&i+fact[k]<1000001)dp[i+fact[k]][k+1]=1; if(dp[i][k])dp[i][k+1]=1; } } for(int n;~scanf("%d",&n);){ if(n<=-1)break; if(n&&dp[n][10]==1){ puts("YES"); }else{ puts("NO"); } } return 0; }