1936.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1936 on 2005-10-31 at 16:13:12 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;

inline int max(int, int);
inline bool match(char, char);

int main()
{
	int c[MAX][MAX];
	char bra[MAX];
	int i, j, k, l;
	
	while(gets(bra) != NULL) {
		if(!strcmp(bra, "end")) {
			return 0;
		} else {
			l = strlen(bra);
			for(i = 0; i <= l; i++) {
				for(j = l-i; j >= 0; j--) {
					if(i == 0 || i == 1) {
						c[i][j] = 0;
					} else {
						c[i][j] = c[i-1][j];
						for(k = 0; k < i-1; k++) {
							if(match(bra[j+k], bra[j+i-1])) {
								c[i][j] = max(c[i][j], c[k][j]+c[i-2-k][j+k+1]+2);
							}
						}
					}
				}
			}
			printf("%d\n", c[l][0]);
		}
	}
	
	return 0;
}

inline int max(int a, int b)
{
	return a > b ? a : b;
}
inline bool match(char b1, char b2)
{
	if(b1 == '(' && b2 == ')') {
		return true;
	} else if(b1 == '[' && b2 == ']') {
		return true;
	} else {
		return false;
	}
}