OR19. 表达式组成方案
描述
对于一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的逻辑表达式，再给定一个结果值。现在可以对这个没有括号的表达式任意加合法的括号，返回得到能有多少种加括号的方式，可以达到这个结果。
给定一个字符串表达式exp及它的长度len，同时给定结果值ret,请返回方案数。保证表达式长度小于等于300。为了防止溢出，请返回答案Mod 10007的值。
"1^0|0|1",7,0
返回：2
C++ 解法, 执行用时: 3ms, 内存消耗: 484KB, 提交时间: 2020-09-06
class Expression {
public:
int countWays(string exp, int len, int ret) {
vector<vector<long long>> t(len, vector<long long>(len, 0)), f = t;
t[0][0] = exp[0] == '1' ? 1 : 0;
f[0][0] = exp[0] == '0' ? 1 : 0;
for (int i = 2; i < len; i += 2)
{
t[i][i] = exp[i] == '1' ? 1 : 0;
f[i][i] = exp[i] == '0' ? 1 : 0;
for (int j = i - 2; j >=0; j -= 2)
{
for (int k = j; k < i; k += 2)
{
if (exp[k+1] == '&')
{
t[j][i] = (t[j][i] + t[j][k] * t[k+2][i]) % 10007;
f[j][i] = (f[j][i] + f[j][k] * f[k+2][i] + t[j][k] * f[k+2][i] + f[j][k] * t[k+2][i]) % 10007;
}
else if (exp[k+1] == '|')
{
f[j][i] = (f[j][i] + f[j][k] * f[k+2][i])%10007;
t[j][i] = (t[j][i] + t[j][k] * t[k+2][i] + t[j][k] * f[k+2][i] + f[j][k] * t[k+2][i])%10007;
}
else
{
t[j][i] = (t[j][i] + t[j][k] * f[k+2][i] + f[j][k] * t[k+2][i])%10007;
f[j][i] = (f[j][i]+ f[j][k] * f[k+2][i] + t[j][k] * t[k+2][i])%10007;
}
}
}
}
return (ret ? t[0][len-1] : f[0][len-1]) % 10007;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 576KB, 提交时间: 2020-09-06
class Expression {
public:
int countWays(string exp, int len, int ret) {
vector<vector<long long>> t(len, vector<long long>(len, 0)), f = t;
for (int i=0; i<len; i+=2){
t[i][i] = exp[i] == '1' ? 1 : 0;
f[i][i] = exp[i] == '0' ? 1 : 0;
for (int j=i-2; j>=0; j-=2){
for (int k = j; k < i; k += 2){
if (exp[k+1] == '&'){
t[j][i] = (t[j][i] + t[j][k]*t[k+2][i])%10007;
f[j][i] = (f[j][i] + f[j][k]*f[k+2][i] + t[j][k]*f[k+2][i] + f[j][k]*t[k+2][i])%10007;
}
else if(exp[k+1] == '|'){
f[j][i] = (f[j][i] + f[j][k]*f[k+2][i])%10007;
t[j][i] = (t[j][i] + t[j][k]*t[k+2][i] + t[j][k]*f[k+2][i] + f[j][k]*t[k+2][i])%10007;
}
else{
t[j][i] = (t[j][i] + t[j][k]*f[k+2][i] + f[j][k]*t[k+2][i])%10007;
f[j][i] = (f[j][i]+ f[j][k]*f[k+2][i] + t[j][k]*t[k+2][i])%10007;
}
}
}
}
return (ret ? t[0][len-1] : f[0][len-1]) % 10007;
}
};