5884. 解出数学表达式的学生分数

5884. 解出数学表达式的学生分数

区间dp

class Solution {
 public:
  int scoreOfStudents(string s, vector<int>& answers) {
    int cnt[1010];
    memset(cnt, 0, sizeof cnt);
    for (auto i : answers) cnt[i]++;

    // 1. 计算正确答案
    stack<int> num, op;
    for (int i = 0; i < s.size(); i++) {
      if (isdigit(s[i])) {
        num.push(s[i] - '0');
        if (op.size() && op.top() == 1) {
          int t = num.top();
          num.pop();
          num.top() *= t;
          op.pop();
        }
      } else {
        if (s[i] == '+') op.push(0);
        if (s[i] == '*') op.push(1);
      }
    }
    int right = 0;
    while (num.size()) {
      right += num.top();
      num.pop();
    }
    // 2. 区间dp，计算所有错误答案
    int n = s.size();
    vector<vector<unordered_set<int>>> f = vector<vector<unordered_set<int>>>(
        n + 10, vector<unordered_set<int>>(n + 10, unordered_set<int>()));

    for (int i = 0; i < n; i++) {
      if (isdigit(s[i])) f[i][i].insert(s[i] - '0');
    }
    for (int len = 3; len <= n; len += 2) {
      for (int i = 0; i + len - 1 < n; i += 2) {
        int j = i + len - 1;
        for (int k = i + 1; k <= j - 1; k += 2) {
          if (isdigit(s[k])) continue;
          unordered_set<int> l = f[i][k - 1], r = f[k + 1][j];
          for (auto lv : l) {
            for (auto rv : r) {
              if (s[k] == '+' && lv + rv <= 1000)
                f[i][j].insert(lv + rv);
              else if (s[k] == '*' && lv * rv <= 1000)
                f[i][j].insert(lv * rv);
            }
          }
        }
      }
    }
    int res = cnt[right] * 5;
    for (auto i : f[0][n - 1]) {
      if (i == right) continue;
      res += cnt[i] * 2;
    }

    return res;
  }
};