题解 | Sum of Factorials

#include <bits/stdc++.h>
using namespace std;

//10!=3628800，已经超越目标，所以结果的和必然在这个范围内，
int factorials[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

int main() {
    int n;
    while (cin >> n) {
        int k = 9;
        while (factorials[k] > n)k--;
        int flag = -1;
        for (; k >= 0; k--) {
            if (n >= factorials[k])n -= factorials[k];
        }
        if (n == 0) {
            flag = 1;
        }
        if (flag == 1)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

注意到，常见阶乘里面15!=1.3076744e+12，经常作为无法处理的极限，这里自然不可能很大的阶乘，且实际上的运算要求中不允许出现重复应用的问题，他既然要实现组装成功，就必然要采用最大到最小的方式，否则是不可能的，然后就可以一次遍历迅速的依靠已知的阶乘结果迅速的得到结果。当然本体的本质来说可以采用背包问题来求解