又捡了一道水题做.曾经有个大牛跟我说：成为大牛的方法是刷水题.我无意成为大牛，但是也要从水题开始刷.
poj-1068 - Parencodings
问题描述：
一组括号 (((( ) ( ) ( ) ) ) )
有两种描述方法：
P方法：4 5 6 6 6 6 - 每一个）前，有几个（
W方法：1 1 1 4 5 6 - 每一个)，向前数几个是跟它匹配的(
要求是根据P求W
问题分析：
解题思路：
1. 虽然没说，但是可以推测出，括号的个数是偶数;第一个一定是（，最后一个一定是）
2. P方法和W方法之间可能存在公式类的规律，但是要寻找不是特别简单
3. 手动分析过程中，我们知道，可以模拟出推到W的过程-模拟法
4. 括号匹配，一定是stack结构
5. 思路就是：根据P还原括号数组，利用stack，推到出W
因为数字描述的是'）'，所以我们先把数组初始化成都是'（'.对于第N个数p，如第一个数4，4表示这个'）'前边的'（'个数，如果再知道前边'）'的个数，那么这个'）'的下标就找到了. N就是前边'）'的个数，所以stack[N+p]=')'.
怎么利用stack推倒出W呢？也很简单,遍历stack数组，当我们发现')'时候，就向前找，另w = 1,c = 0,遇到一个')'加1，同时c加1，说明中间遇到一对(),遇到一个'('减1，当w为0时候，就找到了匹配的'('. c就是个数.
AC源码：
#include <stdio.h> #include <string.h> #define DEBUG 0 int main( void ){ int n_case = 0 , n_number = 0 , _n = 0 , _n_number = 0 , _c = 0 , _sp = 0 , _tmp = 9 , r = 0; int numbers [ 40 ] = { 0 }; int stack [ 40 ] = { 0 }; #if DEBUG freopen( "data" , "r" , stdin); #endif scanf( "%d" , & n_case); while( n_case --) { memset( numbers , 0 , sizeof( numbers)); memset( stack , 0 , sizeof( stack)); scanf( "%d" , & n_number); _n = 0; _n_number = n_number; // 1. get number and build stack while( n_number > 0) { scanf( "%d" , & numbers [ _n ]); stack [ numbers [ _n ] + _n ] = 1; ++ _n; -- n_number; } #if DEBUG for ( _n = 0; _n < _n_number * 2; ++ _n) { printf( "%d " , stack [ _n ]); } printf( " \n "); #endif // 2. retell the process of W-S for ( _n = 0; _n < _n_number * 2; ++ _n) { if ( 0 == stack [ _n ]) continue; _c = 1; r = 1; for ( _sp = _n - 1; _sp > 0; -- _sp) { if ( stack [ _sp ] == 1) { ++ _c; ++ r; } else -- _c; if ( _c == 0) break; } if ( _n == _n_number * 2 - 1) printf( "%d \n " , r); else printf( "%d " , r); } } return 0; }转载于:https://www.cnblogs.com/linucos/archive/2011/10/12/2208567.html
