ICPC練習会2011 Problem.D 6÷2(1+2)
演算子の優先順位がわからないときに、何通り答えがあるかを求める問題。
頑張ってDPを使って解いてみた。
CYK法(Cocke-Younger-Kasami法:文脈自由文法が与えられたときに構文木を導出するアルゴリズム)みたいな手法。
授業で扱ったような気がするけど、実際実装しようとなると、添字の範囲とかが混乱する・・・。
#include <iostream> #include <string> #include <set> #include <vector> #include <cstdlib> using namespace std; typedef set<int> si; string str; unsigned int p; si count() { si num[15][15]; vector<char> op; int c = 0; while(p<str.size()) { char ch = str[p++]; if(ch==')') break; else if(ch=='(') { num[c][0] = count(); c++; } else if('0'<=ch && ch<='9') { int n = ch - '0'; while(p<str.size() && '0'<=str[p] && str[p]<='9') { n = n*10 + str[p++]-'0'; } num[c][0].insert(n); c++; } else { op.push_back(ch); } } for(int j=1;j<c;j++) { for(int i=0;i+j<c;i++) { si &s = num[i][j]; for(int k=0;k<j;k++) { si &a = num[i][k]; si &b = num[i+k+1][j-k-1]; char ch = op[i+k]; for(si::iterator ai=a.begin(); ai!=a.end(); ai++) { for(si::iterator bi=b.begin(); bi!=b.end(); bi++) { if(ch=='+') s.insert(*ai + *bi); if(ch=='-') s.insert(*ai - *bi); if(ch=='*') s.insert(*ai * *bi); if(ch=='/' && *bi!=0) s.insert(div(*ai,*bi).quot); } } } } } return num[0][c-1]; } int main() { while(true) { cin >> str; if(str=="#") break; p = 0; cout << count().size() << endl; } return 0; }