我在一次训练中遇到了这个问题.即我们给出了N不同的值(N<= 100).让我们命名这个数组A[N],这个数组A,我们确信,我们有数组1 A[i]≤10 9.其次,我们已经给数S ,其中S≤10 9.
现在我们必须用这个值来解决经典硬币问题.实际上我们需要找到最小数量的元素,它们将完全相加S.每个元素A都可以无限次使用.
时间限制:1秒
内存限制:256 MB
例:
S = 1000, N = 10
A[] = {1,12,123,4,5,678,7,8,9,10}. The result is 10.
1000 = 678 + 123 + 123 + 12 + 12 + 12 + 12 + 12 + 12 + 4
我试过了什么
我试图用经典的动态编程硬币问题技术来解决这个问题,但是它使用了太多内存并且超出了内存限制.
我无法弄清楚我们应该保留这些价值观.提前致谢.
以下是经典dp硬币问题无法解决的几个测试用例.
S = 1000000000 N = 100
1 373241370 973754081 826685384 491500595 765099032 823328348 462385937
251930295 …我正在尝试用字符串解决一个非常复杂的问题:
给定的字符串最多包含100000个字符,仅包含两个不同的字符"L"和"R".序列"RL"被认为是"坏",并且必须通过应用交换来减少这种情况.
但是,该字符串应被视为循环,因此即使字符串'LLLRRR'也具有由最后'R'和第一'L'形成的'RL'序列.
可以进行两个连续元素的交换.因此,如果n是字符串的长度(字符串为0索引),我们只能交换位置i和i + 1或位置0和n-1上的元素.
目标是找到在字符串中只留下一个错误连接所需的最小交换次数.
对于字符串'RLLRRL',只需一次交换即可解决问题:交换第一个和最后一个字符(因为字符串是圆形的).因此,该字符串将变为具有一个错误连接的"LLLRRR".
我的想法是使用动态编程,并计算任何给定的'L'需要多少交换才能将所有其他'左'放到'L',或者,在'L'的右边.对于任何'R',我计算相同.
该算法在O(N)时间内工作,但不能给出正确的结果.
当我必须交换第一个和最后一个元素时,它不起作用.我应该在算法中添加什么才能使其适用于那些交换？
我正在解决这个问题，即我们给出了数字N，它可以非常大，最多可以有 100000 位数字。
现在我想知道找到这些数字的最有效方法是什么，我认为在大数字中，我最多需要删除 3 位数字才能使数字被 3 整除。
我知道如果数字之和可以被三整除，这个数字可以被三整除，但我想不出我们如何使用它。
我的想法是对字符串进行蛮力并检查我们是否删除了该数字是否可以被 3 整除，但是我的解决方案在复杂的例子中失败了。请给我一些提示。
提前致谢。
我们有 STL（标准模板库）多重集，我们想要实现一个二分搜索，它将为我们提供与某个值 x 相比的第一个小于或等于的元素
从这篇文章：lower_bound == upper_bound中，我们看到我们可以使用标准的 lower_bound 和 upper_bound 来找到比 x 更大的值，或者找到更小的或等于的值。
可以做这样的事吗？