Deu Bracitoi Seqnsia

2445 단어 ojodyssey
코드는 당분간 공개할 수 없다는 원칙에 따라 지금 먼저 기록하고 해금된 후에 문제 번호를 발표한다(차이도 알아낼 수 있을 것 같지만)
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define MAXN 103
#define INF 0x3f3f3f3f
char originalSequence[MAXN];
int bracketLength[MAXN][MAXN];
int bracketBreakChoose[MAXN][MAXN];
int sequenceLength;
bool arePair(char a, char b) { return ((a == '(') && (b == ')')) || ((a == '[') && (b == ']')); }
void init()
{
	for (int i = 0; i < sequenceLength; i++) {
		for (int j = 0; j < sequenceLength; j++) {
			bracketLength[i][j] = INF;
			bracketBreakChoose[i][j] = -1;
		}
	}
}
void dp()
{
	for (int i = 0; i < sequenceLength; i++) {
		bracketLength[0][i] = 2;//length after adding
		bracketBreakChoose[0][i] = i;
	}
	for (int i = 1; i < sequenceLength; i++) {
		for (int j = 0; j < sequenceLength-i ; j++) {
			int tempMin = INF;
			int tempMinPoz = -1;
			if (arePair(originalSequence[j], originalSequence[j+i])) {
				tempMin = (i == 1) ? 2 : bracketLength[i-2][j+1]+2;
				tempMinPoz = -2;//for extraction
			}
			for (int k = 0; k < i; k++) {
				if (bracketLength[k][j] + bracketLength[i-k-1][j+k+1] < tempMin) {
					tempMin = bracketLength[k][j] + bracketLength[i-k-1][j + k+1];
					tempMinPoz = j+k;
				}
			}
			bracketLength[i][j] = tempMin;
			bracketBreakChoose[i][j] = tempMinPoz;
		}
	}
}
void print(int from,int to)
{
	if (from > to)
		return;
	if (from == to) {
		if (originalSequence[from] == '(' || originalSequence[from] == ')')
			printf("()");
		else
			printf("[]");
	}
	else {
		if (bracketBreakChoose[to-from][from] == -2) {
			printf("%c",originalSequence[from]);
			print(from + 1, to - 1);
			printf("%c", originalSequence[to]);
		}
		else {
			print(from, bracketBreakChoose[to-from][from]);
			print(bracketBreakChoose[to-from][from] + 1, to);
		}
	}
}
void solve()
{
	dp();
	print(0, sequenceLength - 1);
	printf("
"); } int main() { while (gets_s(originalSequence) != NULL) { //printf("%s with strlen %d
", originalSequence, strlen(originalSequence)); sequenceLength = strlen(originalSequence); if (sequenceLength == 0) { printf("
"); continue; } init(); solve(); } return 0; }

좋은 웹페이지 즐겨찾기