查找创建满足m个条件的长度为n的序列A的方法数量 [英] Find number of ways to create sequence A of length n satisfying m conditions

问题描述

找到创建满足m个条件的长度为n的序列A的方法的数量.此序列A应该仅由非负数组成.每个条件由三个整数(i，j，k)描述，它们表示max(A [i]，A [j])= k.
保证序列的每个索引至少在一个条件下存在即将有有限数量的此类序列.
n的最大值不超过18，k的最大值不超过20000.
我使用动态编程进行了尝试，但是时间复杂度却是指数级的.您能建议我什么更好的方法来降低时间复杂度吗?

Find number of ways to create sequence A of length n satisfying m conditions. This sequence A should consist of only non negative numbers. Each condition is described by three integers (i,j,k) signifying max(A[i],A[j])=k.
It is guaranteed that each index of the sequence will be there in at least one condition i.e. there will be finite number of such sequences.
The maximum value of n will not exceed 18 and maximum value of k will not exceed 20000.
I tried it using dynamic programming but the time complexity came out to be exponential. Can you suggest me any better approach which will reduce the time complexity?

推荐答案

按照user3386109的建议，将每个输入约束max(A [i]，A [j])= k分解为三个约束:

Following user3386109's suggestion, decompose each input constraint max(A[i], A[j]) = k into three constraints:

• A [i]≤k
• A [j]≤k
• A [i] = k∨A [j] = k

我们可以使用类似DPLL的回溯程序来计算解决方案.首先，相当于单位传播:

We can count solutions using a DPLL-like backtracking procedure. First, the equivalent of unit propagation:

• 给定两个约束A [i]≤k ₁ 和A [i]≤k ₂ ，我们可以使A [i]≤min(k ₁ ，k ₂ )并丢弃另一个.
• 给出两个约束A [i] = k ₁ 和A [i]≤k ₂ ，或者我们可以删除后者(如果k ₁ ≤k ₂ )或声明没有解决方案(否则).
• 给出两个约束A [i]≤k ₁ 和A [i] = k ₂ ∨A [j] = k ₂ ，如果k ₁ < k ₂ ，那么我们可以将后者简化为A [j] = k ₂ .
• 给出两个约束A [i] = k ₁ 和A [i] = k ₂ ∨A [j] = k ₂ ，我们可以删除后者(如果k ₁ = k ₂ )或将其简化为A [j] = k ₂ (否则)

• Given two constraints A[i] ≤ k₁ and A[i] ≤ k₂, we can keep A[i] ≤ min(k₁, k₂) and discard the other.
• Given two constraints A[i] = k₁ and A[i] ≤ k₂, either we can drop the latter (if k₁ ≤ k₂) or declare that there are no solutions (otherwise).
• Given two constraints A[i] ≤ k₁ and A[i] = k₂ ∨ A[j] = k₂, if k₁ < k₂, then we can simplify the latter to A[j] = k₂.
• Given two constraints A[i] = k₁ and A[i] = k₂ ∨ A[j] = k₂, either we can drop the latter (if k₁ = k₂) or simplify it to A[j] = k₂ (otherwise).

如果所有约束都是前两种类型的约束，我们可以通过对非冗余不等式约束右边的每个k取(k + 1)的乘积来计算解决方案的数量.

If all constraints are of the first two types, we can count the number of solutions by taking the product of (k + 1) for each k that is the right-hand side of a non-redundant inequality constraint.

否则，存在约束A [i] = k∨A [j] = k.我们进行两个递归调用:一个具有额外约束A [i] = k，另一个具有额外约束A [i]≤k-1(我们知道A [i]> k是不可能的).

Otherwise, there is a constraint A[i] = k ∨ A[j] = k. We make two recursive calls: one with the extra constraint A[i] = k and one with the extra constraint A[i] ≤ k - 1 (we know that A[i] > k is impossible).

递归树的深度最多为n，因为在单位传播之后，每个子调用都比其父级固定更多的变量.因此，搜索树具有O(2 ⁿ )个节点，每个节点都应该便宜.

The depth of the recursive tree is at most n, since each child call fixes more variables than its parent after unit propagation. Hence the search tree has O(2ⁿ) nodes, each of which should be decently cheap.

这篇关于查找创建满足m个条件的长度为n的序列A的方法数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！