cf:C. Factorials and Powers of Two【dp + 排序 + 选不选板子 + 选若干个数等于已知和的最少数】

分析

先把数组构造出来，用set存保证唯一
然后变成倒排的list
然后dfs，dfs记录当前和，剩余可选，选的个数
如果当前和为n成功
剪枝：剩余可选为0，当前和大于n，当前和+剩余可选和小于n
然后返回的是选或不选当前第一个的最小值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)

总结

选不选板子