表达式组成方案

[编程题]表达式组成方案

热度指数：1533 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个只由0(假)、1(真)、&(逻辑与)、|(逻辑或)和^(异或)五种字符组成的逻辑表达式，再给定一个结果值。现在可以对这个没有括号的表达式任意加合法的括号，返回得到能有多少种加括号的方式，可以达到这个结果。

给定一个字符串表达式exp及它的长度len，同时给定结果值ret,请返回方案数。保证表达式长度小于等于300。为了防止溢出，请返回答案Mod 10007的值。

测试样例：

"1^0|0|1",7,0

返回：2

算法知识视频讲解

Java

Holiday_12138

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)

Java

JustYoung

这题切记要对每一步计算加上取余数的操作 % 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)