← 返回题目列表

AtCoder · icpc2013summer_day4_e

E. 最优 alpha beta 剪枝

中文机器翻译题面 查看原题

问题陈述

抱歉,问题陈述已修改。(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