c++ - C++ 中的 bool 括号

Question

bool 括号问题是计算用括号括起给定二进制表达式以使其计算结果为真的方法的数量。

我根据给出的解释写了一个C++方案here ( small video explanation here )，但它总是返回零。我的代码看起来与第一页上给出的代码非常相似(在编写我的代码之前我没有看)，但它在我的代码不工作的地方工作。我犯了什么错误？

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> vals(n);
    vector<int> ops(n - 1); //ops[n] is the operator
                             //between the nth and (n-1)th values
    char tmp;

    for(int i = 0; i < 2 * n - 1; ++i) {
        if(i % 2 == 0) {
            cin >> vals[i / 2];
        } else {
            cin >> ops[i / 2];
        }
    }

    vector<vector<int> > t(n, vector<int>(n, 0)),
                         f(n, vector<int>(n, 0));

    for(int i = 0; i < n; ++i) {
        t[i][i] = vals[i] == 1;
        f[i][i] = vals[i] == 0;
    }

    const int AND = 6, OR = 1, XOR = 4;

    for(int i = 0; i < n - 2; ++i) {
        for(int j = i + 1; j < n - 1; ++j) {
            for(int k = i; k < j; ++k) {
                cout << endl << i << " " << j << " " << k << endl;
                switch(ops[k]) {
                    case AND:
                        t[i][j] = t[i][k] * t[k + 1][j];  //T & T = T
                        f[i][j] = f[i][k] * f[k + 1][j]   //F & F = F
                                + f[i][k] * t[k + 1][j]   //F & T = F
                                + t[i][k] * f[k + 1][j];  //T & F = F

                    case OR:
                        t[i][j] = t[i][k] * t[k + 1][j]   //etc
                                + f[i][k] * t[k + 1][j]
                                + t[i][k] * f[k + 1][j];
                        f[i][j] = f[i][k] * f[k + 1][j];

                    case XOR:
                        t[i][j] = f[i][k] * t[k + 1][j]
                                + t[i][k] * f[k + 1][j];
                        f[i][j] = f[i][k] * f[k + 1][j]
                                + t[i][k] * t[k + 1][j];
                }

                for(int i = 0; i < n; ++i) {
                    for(int j = 0; j < n; ++j) {
                        cout << t[i][j] << " ";
                    }
                    cout << endl;
                }
            } //k loop
        } //j loop
    } //i loop

    cout << endl << t[0][n - 1];
}

Answer 1

外面的两个循环(i 和j)不是正确的。您在代码中所做的是从表达式的一端开始，向另一端移动(i 循环)，并尝试计算从当前位置开始的越来越宽的子表达式(width j - i，j 循环)。问题在于，为了计算宽度为 k 的表达式的括号变化，您需要其宽度为 k - 1 和更小的子表达式的所有值，其中，在您的解决方案中，您还没有计算(无论如何不是全部)。因此，您依赖于尚未计算且默认为 0 的值，这在这些乘法中为您提供了很好的胖零。

与任何动态规划问题一样，诀窍是构建宽度 k 的所有值只有在您已经计算了宽度 k 的所有相关值之后 - 1。所以，外面的两个循环应该看起来像这样:

//You've calculated width 0 in the loop before, so start at 1.
for(int width = 1; width < n; ++width)
   for(int i = 0, j = i + width; j < n; ++i, ++j)
      //The inner loop looks OK at first glance, 
      //but I haven't looked at it in depth.

请记住，这是未经测试、未实现的代码，它仅基于我对本例中动态规划问题的理解(众所周知，我的理解有时是错误的... ).但是，它应该让您在清理问题方面抢先一步。