首页 > 代码库 > poj 1068 Parencodings
poj 1068 Parencodings
题目链接：http://poj.org/problem?id=1068
思路：
对栈的模拟，将栈中元素视为广义表，如 (((()()())))，可以看做 LS =< a1, a2..., a12 >,对于可以配对的序列，如 <a4, a5>看做一个元素，其 W 值为1；
同理，<a6, a7>为一个元素，其W值为1，< a3, a4, a5, a6, a7, a8, a9, a10 >看做一个元素， 其W值为 <a4, a5> 与 <a6, a7>、< a8, a9 >的W的值的和加 1，即为4;
如此处理，直到求出所有的W值。
代码：
#include <iostream>#include <stack>using namespace std;int main(){ int n; char Record[20]; // 广义表记录 stack<char> A; cin >> n; for ( int i = 0; i < n; ++i ) { int Size, Index = -1; int Count1 = 0, Count2; cin >> Size; for( int j = 0; j < Size; ++j ) { int W = 1, IsMatch = 0; cin >> Count2; for ( int k = 0; k < Count2 - Count1; ++k ) A.push(‘(‘); while ( IsMatch == 0 ) { if ( A.top() == ‘)‘ ) { A.pop(); W += Record[Index--]; } else { A.pop(); IsMatch = 1; } } A.push(‘)‘); Record[++Index] = W; Count1 = Count2; printf("%d ", W ); } printf( "\n" ); } return 0;}
poj 1068 Parencodings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。