小编Voy*_*ger的帖子

问题

输入一个整数数组A，其中1<=A[i]<=1000000.

找到正整数多重集（就像硬币一样）的最小大小（基数）S，使得对于每个A[i]，都存在S其总和等于的子集A[i]。

例子1

输入A = [1,27,28]。

输出2，最小多重集之一是{1,27}。

例子2

输入A=[18,37,42,50]

输出3，唯一的最小多重集是{5,13,37}

此测试用例显示 没有min(A)出现在 中S，并且答案 > ceil(log2(len(A)))。

我的问题

即使len(A)<=10，我也找不到任何正确且确定的算法。有什么解决方案在len(A)10 左右时有效吗？

我只能找到一种在以下情况下有效的算法len(A)<=6：

例如，当 时len(A)==6，从 中删除重复项A。假设 的大小S为5，则以时间复杂度 O(perm(32, 5)) …

给定一个 array A，您可以重复删除长度等于其k总和的任何连续子数组tar。通过此过程输出是否A可以清空。

A是一个整数数组，k是一个正整数，tar是一个整数。

例如，A=[1,2,3,4];k=2;tar=5 然后您可以删除[2,3]fromA使其变为[1,4]。然后你[1,4]从A;中删除 它变得空了。因此，算法应该输出True。

目前我已经找到了一个O(n^2/k*comb(n/k,k))算法。还有更好的吗？

我的算法

首先使用dp，判断是否A[i:j]可以为空，然后枚举最后删除的子数组的所有元素，及时O(comb((j-i)/k, k))，

python3的示例代码，当k为3：

from functools import lru_cache
from itertools import accumulate

def solve(A, k, tar):
    # only works when k = 3
    assert k==3
    presum = list(accumulate(A, initial=0))

    @lru_cache(None)
    def judge(i, j):
        """ 
        find if …

环境

x86-64 gcc 12.2，您可以尝试https://godbolt.org/z/eTvTf7n3n和https://godbolt.org/z/4W7hM3Pzs

代码

#include <type_traits>

// pass
template<std::enable_if_t<!std::is_same_v<int, int>, bool> = 0>
void f1(){
}

// Compilation failed
template<std::enable_if_t<!std::is_same<int, int>::value, bool> = 0>
void f2(){
}


int main()
{
}

问题

为什么功能f1和f2行为不同？is_same_v只是 的恒定时间包装is_same::value，我不明白是什么造成了差异。