问题陈述
抱歉,问题陈述已修改。(12:51 JST)Fox Ciel 正在为一款游戏开发人工智能 (AI)。该博弈被描述为具有 n 个顶点的博弈树 T。 游戏中的每个节点都有一个评估值,表明情况有多好。 该值等于子节点值的最大值乘以-1。叶节点上的值是用 Ciel 的特殊函数计算的——这个函数有点繁重。 因此,她将使用α-β剪枝来获取根节点的评估值,以减少需要计算的叶子节点的数量。
顺便说一句,改变子节点的计算顺序会影响叶节点的计算数量。 因此,Ciel 想知道当她可以以任意顺序评估子节点时,在叶节点中计算的最小和最大次数。 她让你计算叶子节点的最小评估次数和最大评估次数。
添加了伪代码。(13:17 JST)
Ciel 使用以下算法:
function negamax(node, α, β)
if node is a terminal node
return value of leaf node
else
foreach child of node
val := -negamax(child, -β, -α)
if val >= β
return val
if val > α
α := val
return α
[注意] negamax 算法
输入
输入遵循以下格式:
n
p_1 p_2 ... p_n
k_1 t_{11} t_{12} ... t_{1k}
:
:
k_n t_{n1} t_{n2} ... t_{nk}
第一行包含一个整数 n,表示博弈树T的顶点数。
第二行包含 n 整数 p_i,表示顶点的评价值 i.
然后,下一步 n 行包含博弈树T的信息。
k_i 是顶点的子节点数 i,和 t_{ij} 是顶点的子节点的索引 i.
输入遵循以下约束:
2 \leq n \leq 100
-10,000 \leq p_i \leq 10,000
0 \leq k_i \leq 5
2 \leq t_{ij} \leq n
根节点索引为 1.
除叶节点外的评估值始终为 0。这并不意味着非叶节点的评估值是 0。如有必要,您必须计算它们。
叶节点有时的评估值为 0.
博弈树T是树结构。
输出
打印叶节点的最小评估次数和最大评估次数。
请在最小值和最大值之间用空格分隔。
minimum maximum
示例输入 1
3 0 1 1 2 2 3 0 0
样本输入 1 的输出
2 2
示例输入 2
8 0 0 100 100 0 -100 -100 -100 2 2 5 2 3 4 0 0 3 6 7 8 0 0 0
样本输入 2 的输出
3 5
示例输入 3
8 0 0 100 100 0 100 100 100 2 2 5 2 3 4 0 0 3 6 7 8 0 0 0
样本输入 3 的输出
3 4
示例输入 4
19 0 100 0 100 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 2 2 3 0 2 4 5 0 3 6 7 8 3 9 10 11 3 12 13 14 3 15 16 17 2 18 19 0 0 0 0 0 0 0 0 0 0
样本输入 4 的输出
7 12