首页 > 其他 > 详细

poj 1068 Parencodings

时间:2014-10-07 01:49:13      阅读:317      评论:0      收藏:0      [点我收藏+]

题目链接: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

原文:http://www.cnblogs.com/tallisHe/p/4008932.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!