[编程题]表达式得到期望结果的组合种数
- 热度指数：3071 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定一个只由0（假）、1（真）、&（逻辑与）、|（逻辑或）和^（异或）五种字符组成的字符串express，再给定一个布尔值desired。求出express能有多少种组合方式，可以达到desired的结果。并输出你所求出的总方案数对
取模后的值。
输入描述:
输出两行，第一行包含一个只有0、1、&、|和^组成的字符串。其长度小于500，第二行只有一个布尔值，代表desired。
输出描述:
输出一个整数，表示取模后的答案。
示例1
输入
1^0|0|1 false
输出
2
说明
1^((0|0)|1)和1^(0|(0|1))可以得到false
示例2
输入
1 false
输出
0
备注:
时间复杂度,空间复杂度
。
这题可以使用动态规划法来做，思路大概是这样：
1.对于整个表达式来说，最后一步的运算一定是这样的形式——（左子串）运算符（右子串）。
2.我们先任意选取一个运算符作为最后一步，假设选取的运算符为^，要得到的结果为true，那么左右子串的运算结果应该为左真右假，或左假右真。那么对于此运算符作为最后一步的不同组合种数 = 左子串为真的组合种数 * 右子串为假的组合种数 + 左子串为假的组合种数 * 右子串为真的组合种数，可以看到子问题和父问题是相同的。对于其它种类的运算符以及要求得到false的情况可以依此类推。
3.然后对于字符串中每一个运算符作为最后一步的情况分别求出组合数，累加即为总的组合数。
4.从2中看出这题子问题和父问题相同，可以用递归的方式解决，但是我试了，递归时间太长，没能通过所有用例。
5.使用动态规划的方式解决这个问题。我们令trueMatrix[start][end]表示从下标start到end的子串要得到结果true有多少种组合，falseMatrix[start][end]表示从下标start到end的子串要得到结果false有多少种组合。那么我们最后要输出的结果就是trueMatrix[0][length - 1]或者false[0][length - 1]。
6.假设我们要求trueMatrix[start][end]，我们应当遍历其中的运算符，将每一个运算符作为最后一步的组合数累加，即为trueMatrix[start][end]。假设运算符的位置为mid，运算符为'^'，那么对于这个运算符作为最后一步的组合数 = trueMatrix[start][mid - 1] * falseMatrix[mid + 1][end] + falseMatrix[start][mid - 1] * trueMatrix[mid + 1][end]，（左真右假 + 左假右真）。其他运算符依此类推。
7.实现代码如下，我的代码还可以优化，比如矩阵的长宽还可以缩小一半。
public class Main {
public static void main(String[] args) {
String inputString;
boolean desires;
long[][] trueMatrix; // trueMatrix[i][j]表示从i到j的子串要得到true有多少种组合
long[][] falseMatrix;
final long A = 1000000007;
// 获取输入
java.util.Scanner input = new java.util.Scanner(System.in);
inputString = input.nextLine();
desires = input.nextBoolean();
int length = inputString.length();
trueMatrix = new long[length][length];
falseMatrix = new long[length][length];
// 先处理长度为1的子串
for (int i = 0; i < length; i += 2) {
char c = inputString.charAt(i);
if (c == '1') {
trueMatrix[i][i] = 1;
falseMatrix[i][i] = 0;
} else if (c == '0'){
trueMatrix[i][i] = 0;
falseMatrix[i][i] = 1;
} else {
// 如果输入无效就直接返回
System.out.println(0);
return;
}
}
// 从长度为3的子串开始，每次递增2，一直处理到长度为length
for (int subLen = 3; subLen <= length; subLen += 2) {
// 处理所有长度为subLen的子串，从开头为0的子串开始，每次递增2
for (int start = 0; start + subLen <= length; start += 2) {
// 遍历子串中的所有运算符，对每一个运算符求出组合种数，累加到matirx[start][start + subLen -1]上
for (int mid = start + 1; mid < start + subLen; mid += 2) {
char c = inputString.charAt(mid);
// 先得到左真，左假，右真，右假，对每种运算符都要用到这四个值
long leftTrue = trueMatrix[start][mid - 1];
long leftFalse = falseMatrix[start][mid - 1];
long rightTrue = trueMatrix[mid + 1][start + subLen - 1];
long rightFalse = falseMatrix[mid + 1][start + subLen - 1];
if (c == '&') {
// 对于&，要想得到真，左右都是真
trueMatrix[start][start + subLen - 1] += ((leftTrue * rightTrue) % A);
// 要想得到假，左右至少有一个为假
falseMatrix[start][start + subLen - 1] += ((leftFalse * rightTrue) % A)
+ ((leftTrue * rightFalse) % A) + ((leftFalse * rightFalse) % A);
} else if (c == '|') {
// 对于|，想要得到真，左右至少有一个为真
trueMatrix[start][start + subLen - 1] += ((leftTrue * rightTrue) % A)
+ ((leftFalse * rightTrue) % A) + ((leftTrue * rightFalse) % A);
// 要想得到假，左右都是假
falseMatrix[start][start + subLen - 1] += ((leftFalse * rightFalse) % A);
} else if (c == '^') {
// 对于^,要想得到真，左真又假，或者左假右真
trueMatrix[start][start + subLen - 1] += ((leftTrue * rightFalse) % A)
+ ((leftFalse * rightTrue) % A);
// 要想得到假，左右都为真或者假
falseMatrix[start][start + subLen - 1] += ((leftTrue * rightTrue) % A)
+ ((leftFalse * rightFalse) % A);
} else {
// 如果输入不规范就直接返回
System.out.println(0);
return;
}
trueMatrix[start][start + subLen - 1] %= A;
falseMatrix[start][start + subLen - 1] %= A;
}
}
}
// 输出结果
if (desires) {
System.out.println(trueMatrix[0][length - 1]);
}
else {
System.out.println((falseMatrix[0][length - 1]));
}
}
}
发表于 2019-08-10 19:07:13
回复(0)
贴个记忆化递归搜索的dp(分治+dp)
/*
* @Author: RockyHoo
* @Date: 2022-03-15 11:29:54
* @LastEditTime: 2022-03-15 15:27:26
* @LastEditors: Please set LastEditors
* @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
* @FilePath: \DP\Untitled1.cpp
*/
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int maxn=507;
void dfs(string s,int start,int end,long long (*dp_true)[maxn],long long (*dp_false)[maxn]){
if(end-start<0) return;
if(end-start==0){
if(s[start]=='1') dp_true[start][start]=1,dp_false[start][start]=0;
else if(s[start]=='0') dp_false[start][start]=1,dp_true[start][start]=0;
return;
}
int next_sybol_pos=start+1;
for(int i=next_sybol_pos;i<end;i+=2){
if(s[i]=='^'){
if(dp_true[start][i-1]==-1) dfs(s,start,i-1,dp_true,dp_false);
if(dp_false[i+1][end]==-1) dfs(s,i+1,end,dp_true,dp_false);
if( dp_true[start][end]==-1) dp_true[start][end]=0;
if(dp_false[start][end]==-1) dp_false[start][end]=0;
dp_true[start][end]+=((dp_true[start][i-1]*dp_false[i+1][end])%mod+(dp_false[start][i-1]*dp_true[i+1][end])%mod)%mod;
dp_false[start][end]+=((dp_true[start][i-1]*dp_true[i+1][end])%mod+(dp_false[start][i-1]*dp_false[i+1][end])%mod)%mod;
// cout<<"^"<<"i:"<<i<<" start:"<<start<<" end:"<<end<<" dp_true:"<<dp_true[start][end]<<" dp_false:"<<dp_false[start][end]<<endl;
}else if(s[i]=='|'){
if(dp_true[start][i-1]==-1) dfs(s,start,i-1,dp_true,dp_false);
if(dp_false[i+1][end]==-1) dfs(s,i+1,end,dp_true,dp_false);
if( dp_true[start][end]==-1) dp_true[start][end]=0;
if(dp_false[start][end]==-1) dp_false[start][end]=0;
dp_true[start][end]+=((dp_true[start][i-1]*dp_false[i+1][end])%mod+(dp_false[start][i-1]*dp_true[i+1][end])%mod+(dp_true[start][i-1]*dp_true[i+1][end])%mod)%mod;
dp_false[start][end]+=(dp_false[start][i-1]*dp_false[i+1][end])%mod;
// cout<<"|"<<"i:"<<i<<" start:"<<start<<" end:"<<end<<" dp_true:"<<dp_true[start][end]<<" dp_false:"<<dp_false[start][end]<<endl;
}else if(s[i]=='&'){
if(dp_true[start][i-1]==-1) dfs(s,start,i-1,dp_true,dp_false);
if(dp_false[i+1][end]==-1) dfs(s,i+1,end,dp_true,dp_false);
if( dp_true[start][end]==-1) dp_true[start][end]=0;
if(dp_false[start][end]==-1) dp_false[start][end]=0;
dp_true[start][end]+=(dp_true[start][i-1]*dp_true[i+1][end])%mod;
dp_false[start][end]+=((dp_false[start][i-1]*dp_true[i+1][end])%mod+(dp_false[start][i-1]*dp_false[i+1][end])%mod+(dp_true[start][i-1]*dp_false[i+1][end])%mod)%mod;
// cout<<"&"<<"i:"<<i<<" start:"<<start<<" end:"<<end<<" dp_true:"<<dp_true[start][end]<<" dp_false:"<<dp_false[start][end]<<endl;
}
dp_true[start][end]%=mod;
dp_false[start][end]%=mod;
}
}
int main(){
string s,desire;
long long dp_true[maxn][maxn],dp_false[maxn][maxn];
while(cin>>s){
cin>>desire;
memset(dp_true,-1,sizeof(dp_true));
memset(dp_false,-1,sizeof(dp_false));
int n=s.size()-1;
dfs(s,0,n,dp_true,dp_false);
if(desire=="true"){
printf("%lld\n",dp_true[0][n]%mod<0?0:dp_true[0][n]%mod);
}else{
printf("%lld\n",dp_false[0][n]%mod<0?0:dp_false[0][n]%mod);
}
}
return 0;
}
编辑于 2022-03-15 15:57:37
回复(0)
怎么取模都不行，摆烂了，直接unsigned long long😂
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdbool.h>
#define MOD 1000000007
typedef unsigned long long ull;
bool isValid(char *exp, int len) {
if (len % 2 == 0) {
return false;
}
for (int i = 0; i < len; i += 2) {
if (exp[i] != '0' && exp[i] != '1') {
return false;
}
}
for (int i = 1; i < len; i += 2) {
if (exp[i] != '&' && exp[i] != '|' && exp[i] != '^') {
return false;
}
}
return true;
}
int main(void) {
char exp[501], desStr[6];
int len;
bool des;
scanf("%s%s", exp, desStr);
len = strlen(exp);
des = strcmp(desStr, "true") == 0;
if (!isValid(exp, len)) {
printf("0\n");
return 0;
}
ull **t, **f;
t = (ull **) malloc(sizeof(ull *) * len);
f = (ull **) malloc(sizeof(ull *) * len);
for (int i = 0; i < len; i++) {
t[i] = (ull *) calloc(len, sizeof(ull));
f[i] = (ull *) calloc(len, sizeof(ull));
}
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]) % MOD) % MOD;
f[j][i] = (f[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
f[j][i] = (f[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
} else if (exp[k + 1] == '|') {
t[j][i] = (t[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
t[j][i] = (t[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
t[j][i] = (t[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
} else {
t[j][i] = (t[j][i] + (t[j][k] * f[k + 2][i]) % MOD) % MOD;
t[j][i] = (t[j][i] + (f[j][k] * t[k + 2][i]) % MOD) % MOD;
f[j][i] = (f[j][i] + (t[j][k] * t[k + 2][i]) % MOD) % MOD;
f[j][i] = (f[j][i] + (f[j][k] * f[k + 2][i]) % MOD) % MOD;
}
}
}
}
printf("%llu\n", des ? t[0][len - 1] : f[0][len - 1]);
return 0;
}
发表于 2022-01-29 14:11:36
回复(0)
本题也是个范围上的尝试模型，和第20题“打气球的最大分数”异曲同工。我们需要尝试每个运算符最后做运算的情况下所得的结果，而要想进行这个运算符的运算，就必须先得到两侧的运算结果，因此两侧的表达式就可以进入一个范围更小的递归过程，周而复始完成整个表达式的计算。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static final int MOD = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] express = br.readLine().toCharArray();
boolean desired = Boolean.valueOf(br.readLine()).booleanValue();
System.out.println(solve(express, desired));
}
private static int solve(char[] express, boolean desired) {
if(!isValid(express)){
return 0;
}
return (int)dynamicProgramming(express, desired);
}
private static long dynamicProgramming(char[] express, boolean desired) {
long[][] t = new long[express.length][express.length]; // t[i][j]表示express[i:j]上为true时的方案数
long[][] f = new long[express.length][express.length]; // f[i][j]表示express[i:j]上为false时的方案数
// base case区间上只有一个字符时的可能性
for(int i = 0; i < express.length; i += 2){
t[i][i] = express[i] == '1'? 1: 0;
f[i][i] = express[i] == '0'? 1: 0;
}
for(int right = 2; right < express.length; right += 2){
for(int left = right - 2; left >= 0; left -= 2){
// 假设k位置为左部分最后一个数
for(int k = left; k < right; k += 2){
if(express[k + 1] == '&'){
// 要得到true需要两边都是true
t[left][right] += ((t[left][k]*t[k + 2][right]) % MOD) % MOD;
t[left][right] %= MOD;
// 要得到false需要两边至少有一个false
f[left][right] += ((t[left][k]*f[k + 2][right]) % MOD + (f[left][k]*t[k + 2][right]) % MOD + (f[left][k]*f[k + 2][right]) % MOD) % MOD;
f[left][right] %= MOD;
}else if(express[k + 1] == '|'){
// 要得到true需要两边至少有一个true
t[left][right] += ((f[left][k]*t[k + 2][right]) % MOD + (t[left][k]*f[k + 2][right]) % MOD + (t[left][k]*t[k + 2][right]) % MOD) % MOD;
t[left][right] %= MOD;
// 要得到false需要两边都是false
f[left][right] += ((f[left][k]*f[k + 2][right]) % MOD) % MOD;
f[left][right] %= MOD;
}else{
// 要得到true需要两边不同
t[left][right] += ((f[left][k]*t[k + 2][right]) % MOD + (t[left][k]*f[k + 2][right]) % MOD) % MOD;
t[left][right] %= MOD;
// 要得到false需要两边相同
f[left][right] += ((t[left][k]*t[k + 2][right]) % MOD + (f[left][k]*f[k + 2][right]) % MOD) % MOD;
f[left][right] %= MOD;
}
}
}
}
return desired? t[0][express.length - 1]: f[0][express.length - 1];
}
// 检查表达式的合法性
private static boolean isValid(char[] express) {
if(express == null || (express.length & 1) == 0){
return false;
}
for(int i = 0; i < express.length; i += 2){
if(express[i] != '0' && express[i] != '1'){
return false;
}
}
for(int i = 1; i < express.length; i += 2){
if(express[i] != '&' && express[i] != '|' && express[i] != '^'){
return false;
}
}
return true;
}
} 本题为了稳，仍然可以采用先写暴力递归，再将暴力递归改写成动态规划的方式，这里我直接提供一个动态规划的版本。不得不说的是，这个题的用例实在是太魔性了，我取这么多次余最终也逃脱不了用long类型的命运
发表于 2021-12-09 11:02:28
回复(0)
/*
*动态规划
*应有dp_true和dp_false两个表
*如dp_true[1,2]代表了， 从字符串第1个数字到第2个数字，有多少种组合可以为true
*那么本题的答案就应该是desired（为true或false）dp_*[1][n]
*/
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string s;
vector<vector<long long int>> dp_true,dp_false;
long long int A = 1000000007;
long long int dp(int l,int r,bool b){
if(l==r){
if(b==true){
if(s[l]=='1'){
if(dp_true[l][r]==-1) dp_true[l][r]=1;
return 1;
}
else{
if(dp_true[l][r]==-1) dp_true[l][r]=0;
return 0;
}
}
else{
if(s[l]=='0'){
if(dp_false[l][r]==-1) dp_false[l][r]=1;
return 1;
}
else {
if(dp_false[l][r]==-1) dp_false[l][r]=0;
return 0;
}
}
}
long long int ans=0;
if(b==true){
if(dp_true[l][r]!=-1){
return dp_true[l][r];
}
for(int i=l;i<r;i++){
if(isdigit(s[i])){
i++;
}
if(s[i]=='^'){
ans+=((dp(l,i-1,true)*dp(i+1,r,false)+dp(l,i-1,false)*dp(i+1,r,true))%A);
}
else if(s[i]=='|'){
ans+=((dp(l,i-1,true)*dp(i+1,r,false)+dp(l,i-1,false)*dp(i+1,r,true)+dp(l,i-1,true)*dp(i+1,r,true))%A);
}
else if(s[i]=='&'){
ans+=((dp(l,i-1,true)*dp(i+1,r,true))%A);
}
}
//如果dp数组还不存在要储存一下
if(dp_true[l][r]==-1){
dp_true[l][r]=ans%A;
}
return ans%A;
}
//如果b是false的情况
else{
//如果dp数组已知直接返回
if(dp_false[l][r]!=-1){
return dp_false[l][r];
}
for(int i=l;i<r;i++){
if(isdigit(s[i])){
i++;
}
if(s[i]=='^'){
ans+=((dp(l,i-1,true)*dp(i+1,r,true)+dp(l,i-1,false)*dp(i+1,r,false))%A);
}
else if(s[i]=='|'){
ans+=((dp(l,i-1,false)*dp(i+1,r,false))%A);
}
else if(s[i]=='&'){
ans+=((dp(l,i-1,true)*dp(i+1,r,false)+dp(l,i-1,false)*dp(i+1,r,true)+dp(l,i-1,false)*dp(i+1,r,false))%A);
}
}
if(dp_false[l][r]==-1){
dp_false[l][r]=ans%A;
}
return ans%A;
}
}
int main(){
cin>>s;
int n=s.size();
dp_true.resize(n,vector<long long int> (n,-1));
dp_false.resize(n,vector<long long int> (n,-1));
bool desired;
cin>>desired;
cout<<dp(0,n-1,desired);
return 0;
} 最后只能通过70%算例，有没有同学解答下为什么……😪
发表于 2021-03-15 23:45:55
回复(1)
#include<iostream>
using namespace std;
bool valid(string &s) {
if( s.size() & 1 ) {
int n = s.size();
for(int i=0; i<n; i+=2) {
if(s[i]!='1' && s[i] !='0') return false;
}
for(int i=1; i<n; i+=2) {
if(s[i]=='^' || s[i]=='|' || s[i] =='&') continue;
else return false;
}
return true;
}
return false;
}
int p(string &s,bool expected, int l,int r) {
if(l==r) {
if(s[l]=='1') return expected? 1:0;
else return expected? 0:1;
}
int res = 0;
if(expected) {
for(int i=l+1;i<r;i+=2) {
switch(s[i]) {
case '&':{
res += p(s,true,l,i-1)*p(s,true,i+1,r);
break;
}
case '|':{
res += p(s,true,l,i-1 )*p(s,false,i+1,r);
res += p(s,false,l,i-1)*p(s,true,i+1,r);
res += p(s,true,l,i-1 )*p(s,true,i+1,r);
break;
}
case '^':{
res += p(s,true,l,i-1)*p(s,false,i+1,r);
res += p(s,false,l,i-1)*p(s,true,i+1,r);
break;
}
}
}
}else {
for(int i=l+1;i<r;i+=2) {
switch(s[i]) {
case '&':{
res += p(s,false,l,i-1)*p(s,true,i+1,r);
res += p(s,true,l,i-1)*p(s,false,i+1,r);
res += p(s,false,l,i-1)*p(s,false,i+1,r);
break;
}
case '|':{
res += p(s,false,l,i-1)*p(s,false,i+1,r);
break;
}
case '^':{
res += p(s,true,l,i-1)*p(s,true,i+1,r);
res += p(s,false,l,i-1)*p(s,false,i+1,r);
break;
}
}
}
}
return res;
}
int main() {
string s,ress;
bool expected;
cin>>s>>ress;
expected = ress == "true";
if(valid(s)==false ) {
puts("0");
return 0;
}
cout << p(s,expected,0 ,s.size()-1);
return 0;
}
发表于 2021-02-02 16:52:44
回复(0)
我琢磨了2个小时，实在是找不到我分开数字和字符做法错在哪里，一直是70%通过率 我炸了，哪个大佬看出来告诉我一声，万分感谢😣😣😣
bool isValid(const string& exp)
{
if(exp.size()&1==0)
return false;
for(int indx=0;indx<exp.size();indx+=2)
{
if(exp[indx]!='0'&&exp[indx]!='1')
return false;
}
for(int indx=1;indx<exp.size();indx+=2)
{
if(exp[indx]!='&'&&exp[indx]!='|'&&exp[indx]!='^')
return false;
}
return true;
}
int main()
{
const int mod=1000000007;
string s;
bool flag;
cin>>s>>flag;
int len=s.size();
if(len%2==0)
{
cout<<0<<endl;
return 0;
}
if(!isValid(s))
{
cout<<0<<endl;
return 0;
}
int l1=(len+1)/2; //数字的数量
int l2=len-l1;//符号的数量
vector<char> arr2(l2);//arr[i]=k k=0表示& k=1表示| k=2表示^
vector<vector<unsigned long long>> dp_true(l1,vector<unsigned long long>(l1,0)); //dp_true[i][j]=k 表示从数字i到数字j 可以组合的true数量
vector<vector<unsigned long long>> dp_false(l1,vector<unsigned long long>(l1,0));
for(int i=0;i<len;i++)
{
if(i%2==0)
{
if(s[i]!='0' && s[i]!='1')
{
cout<<0<<endl;
return 0;
}
dp_true[i/2][i/2]=(s[i]=='1'?1:0);
dp_false[i/2][i/2]=(s[i]=='0'?1:0);
}
else
arr2[i/2]=s[i];
}
for(int len=2;len<=l1;len++) //采取先计算小区间=》后计算大区间
for(int i=0;i+len<=l1;i++)
{
int j=i+len-1; //区间终点 j
for(int k=i;k<j;k++) //研究最后计算的那个符号
{
if(arr2[k]=='&')
{
dp_true[i][j]=(dp_true[i][j]+dp_true[i][k]*dp_true[k+1][j])%1000000007;//为真的情况 只能是两边都为真
dp_false[i][j]=(dp_false[i][j]+dp_false[i][k]*(dp_true[k+1][j]+dp_false[k+1][j])+dp_true[i][k]*dp_false[k+1][j])%1000000007;//前面为假
}
else if(arr2[k]=='|')
{
dp_false[i][j]=(dp_false[i][j]+dp_false[i][k]*dp_false[k+1][j])%1000000007;//为假的情况 只能是两边都为假
dp_true[i][j]=(dp_true[i][j]+dp_true[i][k]*(dp_true[k+1][j]+dp_false[k+1][j])+dp_false[i][k]*dp_true[k+1][j])%1000000007;//前面为真
}
else
{
dp_true[i][j]=(dp_true[i][j]+dp_true[i][k]*dp_false[k+1][j]+dp_false[i][k]*dp_true[k+1][j])%1000000007;
dp_false[i][j]=(dp_false[i][j]+dp_true[i][k]*dp_true[k+1][j]+dp_false[i][k]*dp_false[k+1][j])%1000000007;
}
}
}
if(flag)
cout<<dp_true[0][l1-1]<<endl;
else
cout<<dp_false[0][l1-1]<<endl;
}
发表于 2020-11-18 01:48:26
回复(2)
将字符和数字从输入中分离出来。
private static long func(String opt, boolean flag) {
if (opt == null || opt == "" || isValid(opt) == false)
return 0;
int intLength = opt.length() / 2;
long[][] T = new long[intLength + 1][intLength + 1]; //true
long[][] F = new long[intLength + 1][intLength + 1]; // false
char[] opts = new char[intLength]; // 记录操作符&| opts[i]对应的是ints[i]后面跟的操作数
int[] ints = new int[intLength + 1]; // 记录被操作的数字
for (int i = 0, j = 0; i < opt.length(); i += 2, j++) {
ints[j] = opt.charAt(i) == '1' ? 1 : 0; //填充操作数
}
for (int i = 1, j = 0; i < opt.length(); i += 2, j++) {
opts[j] = opt.charAt(i); // 填充字符
}
for (int i = ints.length - 1; i >= 0; i--) {
T[i][i] = ints[i] == 0 ? 0 : 1;
F[i][i] = ints[i] == 0 ? 1 : 0;
for (int j = i + 1; j < ints.length; j++) {
for (int k = i; k < j; k++) {
switch (opts[k]) {
case '^':
T[i][j] = (T[i][j] + T[i][k] * F[k + 1][j] % X + F[i][k] * T[k + 1][j] % X) % X;
F[i][j] = (F[i][j] + T[i][k] * T[k + 1][j] % X + F[i][k] * F[k + 1][j] % X) % X;
break;
case '|':
T[i][j] = (T[i][j] + T[i][k] * T[k + 1][j] % X + T[i][k] * F[k + 1][j] % X + F[i][k] * T[k + 1][j] % X) % X;
F[i][j] = (F[i][j] + F[i][k] * F[k + 1][j] % X) % X;
break;
case '&':
T[i][j] = (T[i][j] + T[i][k] * T[k + 1][j] % X) % X;
F[i][j] = (F[i][j] + T[i][k] * F[k + 1][j] % X + F[i][k] * T[k + 1][j] % X + F[i][k] * F[k + 1][j] % X) % X;
break;
}
}
}
}
return flag ? T[0][T.length - 1] : F[0][F.length - 1];
}
发表于 2020-07-24 13:24:24
回复(0)
动态规划
以输入示例1为例
1^0|0|1探索规律：
每个位置值的计算都涉及枚举，时间复杂度O(N3)，空间复杂度很明显O(N2)。
import java.util.*;
public class Main {
public static long mod = 1_000_000_007;
public boolean isValid(char[] exp) {
if (exp.length % 2 == 0) return false;
for (int i = 0; i < exp.length; i += 2) {
if (exp[i] != '0' && exp[i] != '1')
return false;
}
for (int i = 1; i < exp.length; i += 2) {
if (exp[i] != '^' && exp[i] != '&' && exp[i] != '|')
return false;
}
return true;
}
public long num(String express, boolean desired) {
if (express == null || express.equals("")) return 0;
char[] exp = express.toCharArray();
if (!isValid(exp)) return 0;
long [][] t = new long[exp.length][exp.length];
long [][] f = new long[exp.length][exp.length];
for (int i = 0; i < exp.length; i += 2) {
t[i][i] = exp[i] == '1' ? 1 : 0;
f[i][i] = exp[i] == '0' ? 1 : 0;
}
for (int i = 2; i < exp.length; i += 2) {
for (int j = 0; j < exp.length - i; j += 2) {
// j ... i+j
t[j][i + j] = 0;
f[j][i + j] = 0;
for (int k = 0; k < i; k += 2) {
if (exp[j + k + 1] == '^') {
t[j][i + j] += ((t[j][j + k] * f[j + k + 2][i + j]) % mod + (f[j][j + k] * t[j + k + 2][i + j]) % mod) % mod;
t[j][i + j] %= mod;
f[j][i + j] += ((t[j][j + k] * t[j + k + 2][i + j]) % mod + (f[j][j + k] * f[j + k + 2][i + j]) % mod) % mod;
f[j][i + j] %= mod;
} else if (exp[j + k + 1] == '&') {
t[j][i + j] += ((t[j][j + k] * t[j + k + 2][i + j]) % mod) % mod;
t[j][i + j] %= mod;
f[j][i + j] += ((t[j][j + k] * f[j + k + 2][i + j]) % mod + (f[j][j + k] * t[j + k + 2][i + j]) % mod + (f[j][j + k] * f[j + k + 2][i + j]) % mod) % mod;
f[j][i + j] %= mod;
} else if (exp[j + k + 1] == '|') {
t[j][i + j] += ((t[j][j + k] * f[j + k + 2][i + j]) % mod + (f[j][j + k] * t[j + k + 2][i + j]) % mod + (t[j][j + k] * t[j + k + 2][i + j]) % mod) % mod;
t[j][i + j] %= mod;
f[j][i + j] += ((f[j][j + k] * f[j + k + 2][i + j]) % mod) % mod;
f[j][i + j] %= mod;
}
}
}
}
return desired ? t[0][exp.length - 1] : f[0][exp.length - 1];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Main p240 = new Main();
String express = sc.nextLine();
boolean desired = sc.nextBoolean();
long num = p240.num(express, desired);
System.out.println(num);
}
}
发表于 2020-05-07 10:28:18
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-11-16 00:28:07 -
2022-08-26 16:34:47
-
2022-08-24 18:58:43
-
2022-08-23 18:40:25 -
2022-08-21 15:13:54
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
