Cf:c. factors and powers of two [DP + sort + Select Board + select several numbers equal to the minimum number of known sums]

analysis

First construct the array , use set The deposit guarantee is unique
Then it becomes inverted list
then dfs,dfs Record current and , The remaining options , Number of selected
If the current sum is n success
prune ： The remaining options are 0, The current sum is greater than n, The present and + The remaining optional sum is less than n
Then it returns the minimum value of the current first one with or without selection dfs

ac code

import sys
import functools
input = sys.stdin.readline



for _ in range(int(input())):
    n = int(input())
    s = set()
    cnt = 1
    now = 1
    while cnt <= n:
        s.add(cnt)
        now += 1
        cnt *= now
    cnt = 1
    while cnt <= n:
        s.add(cnt)
        cnt *= 2
    lst = tuple(sorted(list(s), reverse = True))


    
    def dfs(tempSum, tempLst, cnt):
        # success
        if tempSum == n:
            return cnt

        # fail 1
        if len(tempLst) == 0 or tempSum > n:
            return 0x7f7f7f7f
        # cut branch, fail 2
        if tempSum + sum(tempLst) < n:
            return 0x7f7f7f7f


        return min(dfs(tempSum + tempLst[0], tempLst[1:], cnt + 1), dfs(tempSum, tempLst[1:], cnt))

    ans = dfs(0, lst, 0)

    if ans < 0x7f7f7f7f:
        print(ans)
    else:
        print(-1)

summary

Choose board or not