[树形dp]与非门 - 2018级算法C2-B题解

发表于 | 分类于 | 热度: 度

题目链接

首先应该可以看出这道题是一道典型的树形动态规划。所以，解题的重点应该是怎样构造从子节点到父节点的状态转移方程，而从子节点推出父节点的过程可以通过dfs实现。

对于每个叶子节点，定义编号为0的节点为它的子节点，则该叶子节点的状态可以由两个编号为0的节点推出。显然编号为0的节点不会出错且可能输出0或1，所以叶子节点的出错情况只有叶子节点本身损坏时才会发生。所以，如果dp数组只以叶子节点的编号和输出情况为索引，状态转移很难实现。所以我们引入当前节点输出是否正确作为dp数组的第三维，定义dp数组为dp[i][j][k]，其中i为当前节点编号，j为当前节点的输出，k为当前节点输出是否正确。

  • 初始化：对于编号为0的节点，该节点输出必定正确，输出可能为0或1，故初始化为dp[0][1][1] = dp[0][0][1] = 1。

  • 状态表示：如果一个节点的子节点某个状态的dp值为0，说明该子节点不会出现该状态，状态转移时不需要考虑该状态。输入A、B的状态可能情况各有4种，通过长度为4的循环即可枚举出一个输入节点的所有可能状态。对于每个可能状态，注意区分理想情况下和可能出错情况下输入的不同，理想情况下的输出计算时要附加注意考虑输入的正确性，即!(j ^ k)；可能出错情况下的输出通过当前节点的输出计算，即k。

  • 状态转移：按照当前状态正确性（即理想输出和可能出错输出是否相等）分类，将子节点的情况数相乘累加，同时考虑取模。

$$
dp[i][j][k] = dp[i][j][k] + (dp[son_A][j_A][k_A] * dp[son_B][j_B][k_B])\qquad k= isEqual(output, realoutput)
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <iostream>
#define ASON son[node][0]
#define BSON son[node][1]
using namespace std;

typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
int son[N][2], errorOutput[N];
LL dp[N][2][2];

inline bool and_not(int a, int b) { return !(a && b); }

void dfs(int node) {
    if (ASON)
        dfs(ASON);
    if (BSON)
        dfs(BSON);

    for (int state1 = 0; state1 < 4; state1++)
        for (int state2 = 0; state2 < 4; state2++) {
            int realinput1 = state1 & 1, correct1 = state1 >> 1, realinput2 = state2 & 1, correct2 = state2 >> 1;
            if (dp[ASON][realinput1][correct1] && dp[BSON][realinput2][correct2]) {
                int input1 = !(realinput1 ^ correct1), input2 = !(realinput2 ^ correct2);
                int output = and_not(input1, input2), realoutput = errorOutput[node] == -1 ? and_not(realinput1, realinput2) : errorOutput[node];

                bool correct = (output == realoutput);

                dp[node][realoutput][correct] = (dp[node][realoutput][correct] + (dp[ASON][realinput1][correct1] * dp[BSON][realinput2][correct2] % MOD)) % MOD;
            }
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    dp[0][0][1] = dp[0][1][1] = 1;
    for (int i = 1; i <= n; i++)
        cin >> son[i][0] >> son[i][1] >> errorOutput[i];

    dfs(1);
    cout << (dp[1][1][0] + dp[1][0][0]) % MOD << endl;

    return 0;
}