如何解决以递归关系为数组元素的大和10^18子集和问题

Question

问题陈述

给你N，数组A和A0的大小，这是数组的第一个元素。数组的其他元素可以通过以下方法计算：

如果我是奇数

• >= 3* Ai-1，如果我是奇数
• Ai=2* Ai-1 +3* Ai-2，则如果我是

I从1到N-1不等

数组遵循一个特殊属性。数组偶数指数处的元素为偶数，奇数指数处的元素为奇数。您的第一个任务是准备这个数组，使数组的和最小化，并且数组遵循所有给定的条件。你会被问到问题。每个查询都由一个整数X组成。如果我们可以通过添加数组A的一些元素来实现它，则必须打印true；如果不可能，则必须打印false。

约束条件

5000

• 1<=A0<=10^6

• A0 even

• 1<=Q<=1000

• 1<=X<=10^18

• 1 <= T <=50
• 1<= N <= <=

样本测试案例

输入

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

修正当我是奇数时，它是乘法而不是加法。

要点：

1. 将不会在数组中出现最多10^18的条目，因为每次我们对下一个数字乘以某个数字时，
2. X小于10^18，所以忽略数组A中大于10^18的数字，每当第一次发生溢出时，就停止计算Ai
3. Ai大于索引处所有元素之和小于i的总和。

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

现在开始解决方案

对于每一个给定的X，K是数组A的大小，数组A的数字按递增的顺序排列，其中Ai<=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";