Deu Bracitoi Seqnsia
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
PAT 1094 구 글 채용메모: 1. subString 왼쪽 닫 고 오른쪽 열 기 2, 0 은 출력 을 보충 해 야 합 니 다. 그렇지 않 으 면 형식 이 잘못 되 었 습 니 다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.