找出创建满足 m 个条件的长度为 n 的序列 A 的多种方法

找出创建满足 m 个条件的长度为 n 的序列 A 的多种方法。该序列 A 应仅包含非负数。每个条件由三个整数 (i,j,k) 描述，表示 max(A[i],A[j])=k。
保证序列的每个索引至少在一种情况下存在，即存在有限数量的此类序列。
n 的最大值不会超过 18，k 的最大值不会超过 20000。
我尝试使用动态编程，但时间复杂度呈指数级增长。您能建议我任何更好的方法来降低时间复杂度吗？

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

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

我们可以使用类似 DPLL 的回溯过程来计算解决方案。首先，单位传播的等价：

• 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) 的乘积来计算解的数量。

否则，存在约束 A[i] = k ∨ A[j] = k。我们进行两次递归调用：一次带有额外约束 A[i] = k，另一次带有额外约束 A[i] ≤ k - 1（我们知道 A[i] > k 是不可能的）。

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.