hiho一下第217周《Logic Expression Tree》题目分析

1
0

《Logic Expression Tree》题目分析

本题是一道树形DP的题目。

我们不妨用v[x]表示以节点x为根的子树的值,f[x]表示为了翻转翻转v[x],需要至少改变多少个运算符。显然f[1]就是最后的答案。

而影响v[x]值的因素只有3个:

1) x节点的运算符。改变x节点的运算符会使f[x]增加1。

2) x左子树的值,v[x.leftchild]。改变v[x.leftchild]会使f[x]增加f[x.leftchild]。

3) x右子树的值,v[x.righthild]。改变v[x.rightchild]会使f[x]增加f[x.rightchild]。

以上3种因素都可能改变/不改变二选一,所以一共有8种组合。我们只需枚举这8中组合,找到哪些组合会使v[x]改变,并从中找到f[x]最小的组合即可。

于是我们得到了一个递归或者说自底向上DP的算法。时间复杂度是O(N)的。

2 answer(s)

0

觉得挺简单的,但是就对了20%,这个代码哪里有问题?

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <limits>

using namespace std;

const double PI = std::atan(1.0) * 4;

const int MAXVAL = 110; 

int leftChild[MAXVAL], rightChild[MAXVAL]; 
string vals[MAXVAL], content[MAXVAL]; 
int minChangedRequest[MAXVAL]; 

void calculate(int node) {
    if (content[node] == "TRUE" || content[node] == "FALSE") {
        minChangedRequest[node] = 1; 
        vals[node] = content[node]; 
    }
    else {
        int lc = leftChild[node], rc = rightChild[node]; 
        calculate(lc); 
        calculate(rc); 

        if (content[node] == "AND") {
            if (vals[lc] == "TRUE" && vals[rc] == "TRUE") 
                vals[node] = "TRUE"; 
            else 
                vals[node] = "FALSE"; 
        }
        else {
            if (vals[lc] == "FALSE" && vals[rc] == "FALSE") 
                vals[node] = "FALSE"; 
            else 
                vals[node] = "TRUE"; 
        }

        if (content[node] == "AND") {
            if (vals[lc] == "TRUE" && vals[rc] == "TRUE") {
                minChangedRequest[node] = min(minChangedRequest[lc], minChangedRequest[rc]); 
            }
            else if (vals[lc] == "FALSE" && vals[rc] == "TRUE") {
                minChangedRequest[node] = 1; 
            }
            else if (vals[lc] == "TRUE" && vals[rc] == "FALSE") {
                minChangedRequest[node] = 1; 
            }
            else if (vals[lc] == "FALSE" && vals[rc] == "FALSE") {
                minChangedRequest[node] = 1 + min(minChangedRequest[lc], minChangedRequest[rc]); 
            }
        }
        else {
            if (vals[lc] == "TRUE" && vals[rc] == "TRUE") {
                minChangedRequest[node] = 1 + min(minChangedRequest[lc], minChangedRequest[rc]);
            }
            else if (vals[lc] == "FALSE" && vals[rc] == "TRUE") {
                minChangedRequest[node] = 1;
            }
            else if (vals[lc] == "TRUE" && vals[rc] == "FALSE") {
                minChangedRequest[node] = 1;
            }
            else if (vals[lc] == "FALSE" && vals[rc] == "FALSE") {
                minChangedRequest[node] = min(minChangedRequest[lc], minChangedRequest[rc]);
            }
        }

    }
}

void init() {
    for (int i = 0; i < MAXVAL; i++) {
        leftChild[i] = 0; 
        rightChild[i] = 0;
        vals[i] = ""; 
        content[i] = "";
        minChangedRequest[i] = 0;
    }
}


int main(int argc, char *argv[]) {
    // for (;;) {
        init();
        int n; cin >> n;

        for (int i = 0; i < n; i++) {
            int parent;

            cin >> parent >> content[i];
            if (parent > 0) {
                if (leftChild[parent - 1] == 0) {
                    leftChild[parent - 1] = i;
                }
                else {
                    rightChild[parent - 1] = i;
                }
            }
        }

        calculate(0);
        cout << minChangedRequest[0] << endl;
    // }

    return 0; 
}
  • 而且这道题是不会出现不能翻转的情况吧?

  • 我也觉得, 除非叶节点有非true或false的,不然都能翻转。

  • 我知道了,只能改变运算符,不能改变叶节点的T或F

  • 原来如此,这道题目的描述有的地方不够清晰和准确。谢谢提示!

  • 添加评论
  • reply
0
  1. 必须要用递归做,自下而上用dp的话找叶节点很麻烦,因为节点的输入顺序可能是打乱的。
  2. 其实到左右子树的value不同时,就可以直接返回1;
  3. 只能改变运算符,所以当遇到叶节点的bool值相同的,就是不能改变,value为-1;
  4. 每次都得判断左右子树是否能变,再做判断。

write answer 切换为英文 切换为中文


转发分享