对于一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的逻辑表达式，再给定一个结果值。现在可以对这个没有括号的表达式任意加合法的括号，返回得到能有多少种加括号的方式，可以达到这个结果。
给定一个字符串表达式exp及它的长度len，同时给定结果值ret,请返回方案数。保证表达式长度小于等于300。为了防止溢出，请返回答案Mod 10007的值。
测试样例：
"1^0|0|1",7,0
返回：2
[编程题]表达式组成方案
class Expression { string str; int DP[333][333][2]; int n; int MOD; void dp() { for(int l=0;l<n;l+=2) { for(int i=0;i+l<n;i+=2) { int v[2] = {0,0}; if(l==0) { int c = str[i] - '0'; DP[i][i+l][c] = 1; DP[i][i+l][c^1] = 0; continue; } for(int j=i;j<i+l;j+=2) { int t[3] = { (DP[i][j][0]%MOD)*(DP[j+2][i+l][0]%MOD), (DP[i][j][0]%MOD)*(DP[j+2][i+l][1]%MOD)+(DP[i][j][1]%MOD)*(DP[j+2][i+l][0]%MOD), (DP[i][j][1]%MOD)*(DP[j+2][i+l][1]%MOD) }; t[0] %= MOD; t[1] %= MOD; t[2] %= MOD; switch (str[j+1]) { case '|': v[0] += t[0]; v[1] += t[1] + t[2]; break; case '&': v[0] += t[0] + t[1]; v[1] += t[2]; break; case '^': v[0] += t[0] + t[2]; v[1] += t[1]; break; } v[0] %= MOD; v[1] %= MOD; } DP[i][i+l][0] = v[0]; DP[i][i+l][1] = v[1]; } } }
public:
int countWays(string exp, int len, int ret) {
str = exp;
n = len;
MOD = 1e4+7; dp(); return DP[0][n-1][ret];
}
};
发表于 2017-12-27 03:26:27
回复(0)
//参考的JustYoung大神 import java.util.Scanner; public class test7 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int len = scanner.nextInt(); String exp = scanner.next(); int ret = scanner.nextInt(); System.out.println(countWays(exp, len, ret)); } } // 三维dp矩阵 dp[i][j][z],表示从i到j计算结果为z的所有方法总和，这里z的取值只有0和1两种。 // 构造dp[i][j][z]的方法是对dp[i][k][z]*dp[k+1][j][z]求和，k取值范围从i到j-1 public static int countNum(int[] nums, char[] ops, int ret) { int n = nums.length; int[][][] d = new int[n][n][2]; for (int i = 0; i < n; i++) { if (nums[i] == 1) { d[i][i][1] = 1; } else { d[i][i][0] = 1; } } for (int x = 1; x < n; x++) { // 外循环是各个数字位 for (int i = 0; i < n - x; i++) { int j = i + x; for (int k = i; k < j; k++) { if (d[i][k][0] != 0 && d[k + 1][j][0] != 0) { int num = cal(0, 0, ops[k]); d[i][j][num] = (d[i][j][num] + d[i][k][0] * d[k + 1][j][0]) % 10007; } if (d[i][k][0] != 0 && d[k + 1][j][1] != 0) { int num = cal(0, 1, ops[k]); d[i][j][num] = (d[i][j][num] + d[i][k][0] * d[k + 1][j][1]) % 10007; } if (d[i][k][1] != 0 && d[k + 1][j][0] != 0) { int num = cal(1, 0, ops[k]); d[i][j][num] = (d[i][j][num] + d[i][k][1] * d[k + 1][j][0]) % 10007; } if (d[i][k][1] != 0 && d[k + 1][j][1] != 0) { int num = cal(1, 1, ops[k]); d[i][j][num] = (d[i][j][num] + d[i][k][1] * d[k + 1][j][1]) % 10007; } } } } return d[0][n - 1][ret]; } public static int countWays(String exp, int len, int ret) { char[] cs = exp.toCharArray(); int[] nums = new int[(len + 1) / 2]; // 存放数字位 char[] ops = new char[(len - 1) / 2]; // 存放操作符位 for (int i = 0; i < len; i++) { if (i % 2 == 0) { nums[i / 2] = Integer.valueOf(cs[i] - '0'); } else { ops[i / 2] = cs[i]; } } return countNum(nums, ops, ret) % 10007; } public static int cal(int a, int b, char op) { if (op == '^') { return a ^ b; } else if (op == '|') { return a | b; } else { return a & b; } } }
编辑于 2016-10-08 22:22:53
回复(0)
/**
可以运用区间DP的思想
对于一个区间[L,R]来说 我们把它以K为中点分为两份
设该表达式为最后算的一个表达式
也就是现在要算的表达式为[L,k][k+1,k+1][k+2,R]有多少种方案为ret。
先讨论符号 例如exp[k-1]='^'
那么我们有真值表
[L,k] [k+2,R] [L,R]
0 0 0
0 1 1
1 0 1
1 1 0
那么[L,R]中 0的方案数=[L,k]中0的方案数*[k+2,R]中0的方案数+[L,k]中1的方案数*[k+2,R]中1的方案数
这样我们就能求出[L,R]的以K分组的方案数了
注意 我这里说的是以K分组
那求[L,R]的方案数就是分别以L,L+2...R-2分组的方案数之和
这就是区间DP的思想
其他运算符以此类推
*/
class Expression {
string str;
int DP[333][333][2];
int n;
int MOD;
///这里DP采用打表的方法
///其实也可用记忆化搜索 可以理解理解区间DP
void dp()
{
///枚举长度
for(int len=0;len<n;len+=2)
///枚举起始点
for(int i=0;i+len<n;i+=2)
{
///v是当前区间ret=0 的和 与 ret=1 的和
int v[2]={0,0};
///len==0时说明现在区间为[i,i] 应初始化为str的值
if(len==0)
{
int c=str[i]-'0';
DP[i][i+len][c]=1;
DP[i][i+len][c^1]=0;
continue;
}
///j为枚举k点
for(int j=i;j<i+len;j+=2)
{
///t为真值表中左右两个区间对应的方案数
///t[0]为 0 0
///t[1]为 0 1 * 0 1
///t[2]为 1 1
int t[3]=
{
(DP[i][j][0]%MOD)*(DP[j+2][i+len][0]%MOD),
(DP[i][j][0]%MOD)*(DP[j+2][i+len][1]%MOD)+(DP[i][j][1]%MOD)*(DP[j+2][i+len][0]%MOD),
(DP[i][j][1]%MOD)*(DP[j+2][i+len][1]%MOD)
};
t[0]%=MOD;
t[1]%=MOD;
t[2]%=MOD;
///处理运算符
switch (str[j+1])
{
case '|':
v[0]+=t[0];
v[1]+=t[1]+t[2];
break;
case '&':
v[0]+=t[0]+t[1];
v[1]+=t[2];
break;
case '^':
v[0]+=t[0]+t[2];
v[1]+=t[1];
break;
}
v[0]%=MOD;
v[1]%=MOD;
}
///为区间赋值
DP[i][i+len][0]=v[0];
DP[i][i+len][1]=v[1];
}
}
public:
int countWays(string exp, int len, int ret)
{
str=exp;
n=len;
MOD=1e4+7;
dp();
return DP[0][n-1][ret];
// write code here
}
};
发表于 2015-08-19 21:40:51
回复(2)
这题切记要对每一步计算加上取余数的操作 % 10007，否则过不了。
思路：构造三维dp矩阵
dp[i][j][z]，表示从i到j计算结果为z的所有方法总和，这里z的取值只有0和1两种。构造dp[i][j][z]的方法为对dp[i][k][z]*dp[k+1][j][z]求和，k取值范围从i到j-1。从矩阵的对角线开始，向右上方计算，和矩阵连乘求乘法次数最少的加括号方式类似。
import java.util.*;
public class Expression {
public int cal(int d1, int d2, char op) {
if (op == '&') {
return d1 & d2;
} else if (op == '|') {
return d1 | d2;
} else {
return d1 ^ d2;
}
}
public int count(int[] digits, char[] ops, int des) {
int n = digits.length;
int[][][] dp = new int[n][n][2];
for (int i = 0; i < n; ++i) {
if (digits[i] == 1) {
++dp[i][i][1];
} else {
++dp[i][i][0];
}
}
for (int x = 1; x < digits.length; ++x) {
for (int i = 0; i < digits.length - x; ++i) {
int j = i + 1 + x - 1;
for (int k = i; k < j; ++k) {
if (dp[i][k][0] != 0 && dp[k + 1][j][0] != 0) {
int num = cal(0, 0, ops[k]);
dp[i][j][num] = (dp[i][j][num] + dp[i][k][0] * dp[k + 1][j][0]) % 10007;
}
if (dp[i][k][0] != 0 && dp[k + 1][j][1] != 0) {
int num = cal(0, 1, ops[k]);
dp[i][j][num] = (dp[i][j][num] + dp[i][k][0] * dp[k + 1][j][1]) % 10007;
}
if (dp[i][k][1] != 0 && dp[k + 1][j][0] != 0) {
int num = cal(1, 0, ops[k]);
dp[i][j][num] = (dp[i][j][num] + dp[i][k][1] * dp[k + 1][j][0]) % 10007;
}
if (dp[i][k][1] != 0 && dp[k + 1][j][1] != 0) {
int num = cal(1, 1, ops[k]);
dp[i][j][num] = (dp[i][j][num] + dp[i][k][1] * dp[k + 1][j][1]) % 10007;
}
}
}
}
return dp[0][n - 1][des];
}
public int countWays(String exp, int len, int ret) {
// write code here
char[] exps = exp.toCharArray();
int[] digits = new int[(exps.length + 1) / 2];
char[] ops = new char[(exps.length - 1) / 2];
for (int i = 0; i < exps.length; ++i) {
if (i % 2 == 0) {
digits[i / 2] = Integer.valueOf(exps[i] - '0');
} else {
ops[i / 2] = exps[i];
}
}
return count(digits, ops, ret) % 10007;
}
}
发表于 2016-08-30 19:26:03
回复(4)
import java.util.*;
// DP[i][j][0/1]：区间DP, 结果就01两种
public class Expression {
public int countWays(String exp, int len, int ret) {
char[] s = exp.toCharArray();
int n = s.length, mod = 10007;
int[][][] dp = new int[n][n][2];
for (int i = n - 1; i >= 0; i -= 2) {
dp[i][i][s[i] - '0'] = 1;
for (int j = i + 2; j < n; j += 2) {
for (int k = i; k + 2 <= j; k += 2) { // 枚举分割点
int op = s[k + 1], cnt0 = 0, cnt1 = 0;
int a0 = dp[i][k][0], a1 = dp[i][k][1];
int b0 = dp[k + 2][j][0], b1 = dp[k + 2][j][1];
if (op == '&') {
cnt0 += a0 * (b0 + b1) + a1 * b0;
cnt1 += a1 * b1;
} else if (op == '|') {
cnt0 += a0 * b0;
cnt1 += a0 * b1 + a1 * (b0 + b1);
} else if (op == '^') {
cnt0 += a0 * b0 + a1 * b1;
cnt1 += a0 * b1 + a1 * b0;
}
dp[i][j][0] = (dp[i][j][0] + cnt0) % mod;
dp[i][j][1] = (dp[i][j][1] + cnt1) % mod;
}
}
}
return dp[0][n - 1][ret];
}
}
发表于 2025-10-24 09:18:05
回复(0)
class Expression {
public:
bool isValid(string exp,int len)
{
if(len%2==0) return false;
for(int i=0;i<len;++i)
{
if(i%2==0)
{
if(exp[i]!='0'&&exp[i]!='1') return false;
}
else{
if(exp[i]!='^'&&exp[i]!='|'&&exp[i]!='&')return false;
}
}
return true;
}
int countWays(string exp, int len, int ret) {
// write code here
int mod = 1e4+7;
if(!isValid(exp,len)) return 0;
vector<vector<long long >>t(len,vector<long long>(len));
vector<vector<long long>>f(len,vector<long long>(len));
t[0][0] = exp[0]== '0' ? 0 : 1;
f[0][0] = exp[0]== '0' ? 1 : 0;
for(int i=2;i<len;i+=2)
{
t[i][i] = exp[i] == '0' ? 0 : 1;
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][k]*t[k+2][i])%mod;
f[j][i] += (t[j][k]*f[k+2][i]+f[j][k]*f[k+2][i]+f[j][k]*t[k+2][i])%mod;
}
else if(exp[k+1]=='|')
{
t[j][i] += (t[j][k]*(f[k+2][i]+t[k+2][i])+ f[j][k]*t[k+2][i])%mod;
f[j][i] += (f[j][k]*f[k+2][i])%mod;
}
else{
t[j][i] += (t[j][k]*f[k+2][i]+f[j][k]*t[k+2][i])%mod;
f[j][i] += (t[j][k]*t[k+2][i]+f[j][k]*f[k+2][i])%mod;
}
}
}
return ret ? (t[0][len-1]%mod):(f[0][len-1]%mod);
}
};
发表于 2020-04-29 17:06:16
回复(0)
class Expression {
public:
int bit(int left,char op,int right){
if(op=='|') return left|right;
if(op=='^') return left^right;
return left&right;
}
int countWays(string exp, int len, int ret) {
int n=len/2+1;
//dp[i][j][k]表示从i到j结果为k的方案数
vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(2,0)));
string num="",op="";//需要先把数字和运算符分开
for(int i=0;i<len;++i)
if(i%2) op+=exp[i];
else num+=exp[i];
//初值
for(int i=0;i<n;++i)
dp[i][i][num[i]-'0']=1;
for(int length=1;length<n;++length)//长度
for(int left=0;left<n-length;++left){//左端点
int right=left+length;//右端点
for(int mid=left;mid<right;++mid)//加括号的方法可以为(left-mid) op (mid+1,right)，方案数为二者相乘
for(int i=0;i<=1;++i)//枚举0，1
for(int j=0;j<=1;++j){//枚举0，1
int k=bit(i,op[mid],j);//k为 i op j 结果
//left-right结果为k的方案数为 left---mid 结果为 i 的方案数乘以 mid+1---right 结果为 j 的方案数相乘
dp[left][right][k]=(dp[left][right][k]+dp[left][mid][i]*dp[mid+1][right][j]) % 10007;
}
}
return dp[0][n-1][ret];
}
};
发表于 2019-03-17 20:41:26
回复(0)
#include<iostream>
#include<vector>
using namespace std;
#define M 10007
#define N 301
/*
for(k=i;k<=j;k+=2){
if(i==j){
ret[i][j][1]=(exp[i]=='1'?1:0);
ret[i][j][0]=(exp[i]=='1'?0:1);
}//if
else{
switch(exp[k+1]){
case '|':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0])%M;
ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
ret[i][k][1]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][1])%M;
break;
case '^':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][1])%M;
ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
ret[i][k][1]*ret[k+2][j][0])%M;
break;
case '&':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][0]+
ret[i][k][0]*ret[k+2][j][1])%M;
ret[i][j][1]+=(ret[i][k][1]*ret[k+2][j][1])%M;
break;
}//switch
}//else
}//for
*/
int fun1(string exp, int len, int ret){
int result[N][N][2];
int inc=0,i=0,k=0,j=0;
for(inc=0;inc<len;inc+=2){
for(i=0;i<len;i+=2){
j=i+inc;
for(k=i;k<=j;k+=2){
if(i==j){
result[i][j][1]=(exp[i]=='1'?1:0);
result[i][j][0]=(exp[i]=='1'?0:1);
}//if
else{
switch(exp[k+1]){
case '|':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0])%M;
result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
result[i][k][1]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][1])%M;
break;
case '^':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][1])%M;
result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
result[i][k][1]*result[k+2][j][0])%M;
break;
case '&':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][0]+
result[i][k][0]*result[k+2][j][1])%M;
result[i][j][1]+=(result[i][k][1]*result[k+2][j][1])%M;
break;
}//switch
}//else
}//for
}//start
}//increment
return result[0][len-1][ret];
}
int main(){
int n=0;
string A="0|0|0";
cout<<fun1(A,5,0)<<endl;
return 0;
}
#include<vector>
using namespace std;
#define M 10007
#define N 301
/*
for(k=i;k<=j;k+=2){
if(i==j){
ret[i][j][1]=(exp[i]=='1'?1:0);
ret[i][j][0]=(exp[i]=='1'?0:1);
}//if
else{
switch(exp[k+1]){
case '|':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0])%M;
ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
ret[i][k][1]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][1])%M;
break;
case '^':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][1])%M;
ret[i][j][1]+=(ret[i][k][0]*ret[k+2][j][1]+
ret[i][k][1]*ret[k+2][j][0])%M;
break;
case '&':
ret[i][j][0]+=(ret[i][k][0]*ret[k+2][j][0]+
ret[i][k][1]*ret[k+2][j][0]+
ret[i][k][0]*ret[k+2][j][1])%M;
ret[i][j][1]+=(ret[i][k][1]*ret[k+2][j][1])%M;
break;
}//switch
}//else
}//for
*/
int fun1(string exp, int len, int ret){
int result[N][N][2];
int inc=0,i=0,k=0,j=0;
for(inc=0;inc<len;inc+=2){
for(i=0;i<len;i+=2){
j=i+inc;
for(k=i;k<=j;k+=2){
if(i==j){
result[i][j][1]=(exp[i]=='1'?1:0);
result[i][j][0]=(exp[i]=='1'?0:1);
}//if
else{
switch(exp[k+1]){
case '|':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0])%M;
result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
result[i][k][1]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][1])%M;
break;
case '^':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][1])%M;
result[i][j][1]+=(result[i][k][0]*result[k+2][j][1]+
result[i][k][1]*result[k+2][j][0])%M;
break;
case '&':
result[i][j][0]+=(result[i][k][0]*result[k+2][j][0]+
result[i][k][1]*result[k+2][j][0]+
result[i][k][0]*result[k+2][j][1])%M;
result[i][j][1]+=(result[i][k][1]*result[k+2][j][1])%M;
break;
}//switch
}//else
}//for
}//start
}//increment
return result[0][len-1][ret];
}
int main(){
int n=0;
string A="0|0|0";
cout<<fun1(A,5,0)<<endl;
return 0;
}
发表于 2017-07-10 14:02:53
回复(0)
//可以动态规划 //经典类型： //0-0 1-1 2-2 3-3 步长为1 //0-1 1-2 2-3 步长为2 //0-2 1-3 步长为3 //0-3 步长为4 //可以先把数字和运算符分别放在A和B中 //dp[i][j][0] i~j中能形成0的有多少种 //dp[i][j][1] i~j中能形成1的有多少种 //0<=a,b<=1 OP=&,|,^ //dp[i][j][a OP b] += (dp[i][k][a] * dp[k + 1][j][b]) % MOD; // i<=k<j; 0<=i,j<=A.size(); OP = B[k] #include <iostream> #include <string> #include <cstring> using namespace std; class Expression { public: const int MOD = 10007; int dp[151][151][2]; int ec(int a, int b, char op){ switch(op){ case '&': return a && b; case '|': return a || b; case '^': return ( (a ^ b) != 0); throw "bad op"; } return 0; } void calc(int i, int j, int k, char op) { for(int a = 0; a < 2; a++) for(int b = 0; b < 2; b++){ int c = ec(a,b,op); dp[i][j][c] += (dp[i][k][a] * dp[k + 1][j][b]) % MOD; dp[i][j][c] %= MOD; } } int countWays(string exp, int len, int ret) { // write code here memset(dp, 0, sizeof(dp)); string A; string B; for (int i = 0; i < len; i++) { if (i & 1) { B += exp.substr(i, 1); } else { A += exp.substr(i, 1); } } for (int i = 0; i < A.size(); i++) for (int k = 0; k < 2; k++) dp[i][i][k] = ((A[i] - '0') == k); for (int step = 2; step <= A.size(); step++) { for (int i = 0; i < A.size(); i++) { int j = i + step - 1; if (j >= A.size()) break; for (int k = i; k < j; k++) { calc(i,j,k, B[k]); } } } return dp[0][A.size() - 1][ret]; } }; #ifdef LOCAL int main() { Expression exp; cout << exp.countWays("1^0|0|1", 7, 0) << endl; } #endif
发表于 2017-05-21 10:20:48
回复(0)
public static int countWays(String exp, int len, int ret) {
int n=len/2+1;
int[][][] dp=new int[n][n][2];//dp[l][r][p],从l到r范围，可以得到p结果的个数
char[] op=new char[n-1];
int[] num=new int[n];
for(int i=0;i<len-1;i+=2){
num[i/2]=exp.charAt(i)-'0';
op[i/2]=exp.charAt(i+1);
}
num[n-1]=exp.charAt(len-1)-'0';
for(int l=0;l<n;l++){
for(int i=0;i+l<n;i++){
if(l==0){
dp[i][i][num[i]]=1;
dp[i][i][num[i]^1]=0;
}
else{
int n0=0,n1=0;
for(int j=i;j<i+l;j++){
int p00,p01,p11;
p00=(dp[i][j][0]%10007)*(dp[j+1][i+l][0]%10007)%10007;
p01=(dp[i][j][0]%10007)*(dp[j+1][i+l][1]%10007)%10007+(dp[i][j][1]%10007)*(dp[j+1][i+l][0]%10007)%10007;
p11=(dp[i][j][1]%10007)*(dp[j+1][i+l][1]%10007)%10007;
switch(op[j]){
case '|':
n0+=p00;
n1+=p01+p11;
break;
case '&':
n0+=p00+p01;
n1+=p11;
break;
case '^':
n0+=p00+p11;
n1+=p01;
break;
}
}
n0%=10007;
n1%=10007;
dp[i][i+l][0]=n0;
dp[i][i+l][1]=n1;
}
}
}
return dp[0][n-1][ret];
}
发表于 2017-03-21 13:33:31
回复(0)
//哈哈，使用区间dp的算法，终于还是通过了，虽然参考了网上的其他代码
//
// Created by Qiu on 2016-11-21.
//
#include <iostream>
#include <cstring>
using namespace std;
class Expression {
public:
int countWays(string exp, int len, int ret) {
// write code here
int mod = 1e4 + 7;
int dp[len][len][2];
memset(dp, 0, len * len * 2 * sizeof(int));
//区间长度
for (int s = 0; s < len; s += 2) {
//开始枚举的起点
for (int i = 0; i + s < len; i += 2) {
int v[2] = { 0, 0 };
if (s == 0) {
int c = exp[i] - '0';
dp[i][i][c] = 1;
dp[i][i][c^1] = 0;
//真是***啊，这里不加continue怎么可以啊
continue;
}
//j表示的是中间的分界点
for (int j = i; j < i + s; j += 2) {
int t[3] = {
(dp[i][j][0] % mod) *
(dp[j+2][i+s][0] % mod),
(dp[i][j][0] % mod) *
(dp[j+2][i+s][1] % mod) + (dp[i][j][1] % mod) * (dp[j+2][i+s][0] %
mod),
(dp[i][j][1] % mod) *
(dp[j+2][i+s][1] % mod)
};
t[0] %= mod;
t[1] %= mod;
t[2] %= mod;
switch(exp[j+1]) {
case '|':
v[0] += t[0];
v[1] += t[1] + t[2];
break;
case '&':
v[0] += t[0] + t[1];
v[1] += t[2];
break;
case '^':
v[0] += t[0] + t[2];
v[1] += t[1];
break;
default:
break;
}
v[0] %= mod;
v[1] %= mod;
}
dp[i][i+s][0] = v[0];
dp[i][i+s][1] = v[1];
}
}
return dp[0][len-1][ret];
}
};
int main() {
string exp = "1^0|0|1";
Expression ex;
cout << ex.countWays(exp, 7, 0);
return 0;
}//
// Created by Qiu on 2016-11-21.
//
#include <iostream>
#include <cstring>
using namespace std;
class Expression {
public:
int countWays(string exp, int len, int ret) {
// write code here
int mod = 1e4 + 7;
int dp[len][len][2];
memset(dp, 0, len * len * 2 * sizeof(int));
//区间长度
for (int s = 0; s < len; s += 2) {
//开始枚举的起点
for (int i = 0; i + s < len; i += 2) {
int v[2] = { 0, 0 };
if (s == 0) {
int c = exp[i] - '0';
dp[i][i][c] = 1;
dp[i][i][c^1] = 0;
//真是***啊，这里不加continue怎么可以啊
continue;
}
//j表示的是中间的分界点
for (int j = i; j < i + s; j += 2) {
int t[3] = {
(dp[i][j][0] % mod) *
(dp[j+2][i+s][0] % mod),
(dp[i][j][0] % mod) *
(dp[j+2][i+s][1] % mod) + (dp[i][j][1] % mod) * (dp[j+2][i+s][0] %
mod),
(dp[i][j][1] % mod) *
(dp[j+2][i+s][1] % mod)
};
t[0] %= mod;
t[1] %= mod;
t[2] %= mod;
switch(exp[j+1]) {
case '|':
v[0] += t[0];
v[1] += t[1] + t[2];
break;
case '&':
v[0] += t[0] + t[1];
v[1] += t[2];
break;
case '^':
v[0] += t[0] + t[2];
v[1] += t[1];
break;
default:
break;
}
v[0] %= mod;
v[1] %= mod;
}
dp[i][i+s][0] = v[0];
dp[i][i+s][1] = v[1];
}
}
return dp[0][len-1][ret];
}
};
int main() {
string exp = "1^0|0|1";
Expression ex;
cout << ex.countWays(exp, 7, 0);
return 0;
}
发表于 2016-11-21 19:55:35
回复(0)
import java.util.*;
public class Expression {
public int countWays(String exp, int len, int ret) {
// write code here
int[][][] dp = new int[len][len][2];
final int MOD = 10007;
//枚举长度
for(int l=0; l<len; l+=2){
//枚举起点
for(int i=0; i+l<len; i+=2){
int[] v = {0,0};
if(l==0){
int c = exp.charAt(i) - '0';
dp[i][i][c] = 1;
dp[i][i][c^1] = 0;
}
else{
//枚举中点
for(int j=i; j<i+l; j+=2){
int[] t = new int[3];
t[0] = ((dp[i][j][0]%MOD)*(dp[j+2][i+l][0]%MOD))%MOD;
t[1] = ((dp[i][j][1]%MOD)*(dp[j+2][i+l][0]%MOD) + (dp[i][j][0]%MOD)*(dp[j+2][i+l][1]%MOD))%MOD;
t[2] = ((dp[i][j][1]%MOD)*(dp[j+2][i+l][1]%MOD))%MOD;
char c = exp.charAt(j+1);
if(c == '&'){
v[0] += t[0] + t[1];
v[1] += t[2];
}else if(c == '|'){
v[0] += t[0];
v[1] += t[1] + t[2];
}else if(c == '^'){
v[0] += t[0] + t[2];
v[1] += t[1];
}
v[0] %= MOD;
v[1] %= MOD;
}
dp[i][i+l][0] = v[0];
dp[i][i+l][1] = v[1];
}
}
}
return dp[0][len-1][ret];
}
}
发表于 2016-04-15 16:30:40
回复(0)
class Expression
{
public:
int countWays(string exp, int len, int ret)
{
vector<vector<vector<long long>>>
table(2, vector<vector<long long>>(len, vector<long
long>(len, -1)));
int tmp= funCore(exp, 0, len - 1, ret,table);
return (tmp % 10007);
}
int funCore(string &exp, int beg, int end, int t,
vector<vector<vector<long long>>> &table)
{
if (table[t][beg][end] !=-1)
return table[t][beg][end];
if (beg == end)
{
if (exp[beg] == '0' + t)
{
table[t][beg][beg] = 1;
return 1;
}
else
{
table[t][beg][beg] = 0;
return 0;
}
}
long long ret = 0;
for (int i = beg + 1; i <= end - 1; i += 2)
{
switch (exp[i])
{
case '|':
if (t == 1)
{
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 1, table);
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 0, table);
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 1, table);
}
else
{
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 0, table);
}
break;
case '&':
if (t == 0)
{
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 1, table);
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 0, table);
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 0, table);
}
else
{
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 1, table);
}
break;
case '^':
if (t == 1)
{
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 1, table);
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 0, table);
}
else
{
ret = ret + funCore(exp, beg, i - 1, 1, table)
* funCore(exp, i + 1, end, 1, table);
ret = ret + funCore(exp, beg, i - 1, 0, table)
* funCore(exp, i + 1, end, 0, table);
}
break;
}
}
table[t][beg][end] = ret % 10007;
return ret % 10007;
}
};
发表于 2015-08-07 16:33:14
回复(0)
问题信息
通过挑战的用户
查看代码
相关试题
-
评论(100) 来自面试常考算法题(十)-经...
-
评论(47) 来自面试常考算法题(十)-经...
-
评论(44) 来自面试常考算法题(十)-经...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
