arrays - 如何解决具有递归关系作为数组元素的大和 10^18 的子集和问题

Question

问题陈述

给定 N(数组 A 的大小)和 A0(数组的第一个元素)。数组的其他元素可以通过以下方式计算:

• A[i] >= 3 * A[i-1] ，如果 i 是奇数

• A[i] = 2 * A[i-1] + 3 * A[i-2] ，如果 i 是偶数

i 从 1 到 N - 1

数组遵循一个特殊的属性。 数组中偶数索引处的元素为偶数，数组奇数索引处的元素为奇数。您的首要任务是准备此数组，使数组的总和最小，并且数组符合所有给定条件。 你有 Q 个问题。每个查询都包含一个整数 X。如果我们可以通过添加数组 A 的一些元素来实现它，则必须打印 true，如果不可能则打印 false。

约束

• 1 <= T <=50
• 1<= N <= 5000
• 1<=A0<=10^6
• A0 是偶数
• 1<=Q<=1000
• 1<=X<=10^18

示例测试用例

输入

1
4 2
5
3 27 36 68 88

输出

false
true
false
true
true

解释 - 数组元素是 [2,7,20,61]

我尝试了一种简单的 dp 方法，但收到了超出内存限制的消息。

Answer 1

A[i] >= 3*A[i-1] , if i is odd

当 i 为奇数时更正它是乘法而不是加法

要点:

1. 数组中最多 10^18 的条目不会太多，因为每次我们都乘以某个数字以获得下一个数字
2. X小于10^18所以忽略数组A中大于10^18的数，每当第一次溢出时停止计算A[i]

3. A[i] 大于索引小于 i 的所有元素的总和

   A[i] > A[i-1]+A[i-2]......A[0]
   

现在开始解决方案
对于每个给定的 X ， K 是数组 A 的大小，其中数字按递增顺序排列，其中 A[i]<=10^18

for(i=k;i>=0;i--)
{
    if(X>=A[i])
    X-=A[i];
}

if(X==0)
    cout<<"true\n";
else
    cout<<"false\n";