本题是一道树形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)的。
觉得挺简单的，但是就对了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
原来如此，这道题目的描述有的地方不够清晰和准确。谢谢提示！
谢谢！