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