本文作者:Zhang, Xuheng 本文分类:编程学习笔记 浏览:224
阅读时间:1894字, 约2-3分钟
(这题有点难)


这道题的步骤很简单:
①:将式子从+(x)的形式变成的带有空的形式
②:将式子从中缀表达式化作后缀表达式
③:进行动态规划
状态转移方程:
设f[i][0]表示第i个空,能填0,f[i][1]表示第i个空,能填1
那么转移方程就出来了:
switch(w_c[i]){ case '+':{ f[top-1][1] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][1] * f[top-1][1])%10007; f[top-1][0] = (f[top][0] * f[top-1][0]) % 10007; break; } case '*':{ f[top-1][0] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][0] * f[top-1][0])%10007; f[top-1][1] = (f[top][1] * f[top-1][1]) % 10007; break; } }
代码如下:
#include <cstdio> #include <stack> #include <iostream> using namespace std; int i,j,n,m; string s,w_c; char str[100001],first[3] = {'(','+','*'}; int f[100001][2]; stack<char> op; int OPS(char a){ int i; for(i=0;i<3;i++){ if(a == first[i]) return i; } return -1; } inline void ChangeS(){ int i; for(i=0;i<n;i++){ if(str[i] == '(') s.push_back(str[i]); else if(str[i] == ')' && str[i-1] != ')') s+="_)"; else if(str[i]!=')' && str[i-1] != ')') { s.push_back('_'); s.push_back(str[i]); } else s.push_back(str[i]); } if(s.at(s.size()-1)!=')') s.push_back('_'); } inline void ChangeE(){ size_t i; char t; for(i=0;i<s.size();i++){ t = s.at(i); if(t == '_') w_c.push_back(t); else{ if(t!=')'){ if(t=='(') op.push(t); else{ if(op.empty()) op.push(t); else{ while((!op.empty())&& OPS(op.top())>=OPS(t)) { w_c.push_back(op.top()); op.pop(); } op.push(t); } } } else{ while((!op.empty()) && op.top()!='('){ w_c.push_back(op.top()); op.pop(); } op.pop(); } } } while(!op.empty()){ w_c.push_back(op.top()); op.pop(); } } void work(){ size_t i,top(0); size_t l = w_c.size(); for(i=0;i<l;i++) { if(w_c[i] == '_'){ f[top][0] = f[top][1] = 1; top++; } else{ --top; switch(w_c[i]){ case '+':{ f[top-1][1] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][1] * f[top-1][1])%10007; f[top-1][0] = (f[top][0] * f[top-1][0]) % 10007; break; } case '*':{ f[top-1][0] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][0] * f[top-1][0])%10007; f[top-1][1] = (f[top][1] * f[top-1][1]) % 10007; break; } } } } printf("%d",f[top-1][0]); } int main(){ scanf("%d",&n); scanf("%s",str); ChangeS(); ChangeE(); //for(i=0;i<=w_c.length();i++) printf("%c",w_c[i]); work(); return 0; }
关于作者Zhang, Xuheng
- 还没有填写个人简介
- Email: hy23682@126.com
- 注册于: 2020-04-07 05:11:14
主题操作记录
2020.5.8 13:44 审核通过