Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

果然,我也是少一個\n就WA。。。服了这题

Posted by KatrineYang at 2016-07-23 19:49:25 on Problem 1141
In Reply To:WA的童鞋 ,别忘了"\n",血得教训 Posted by:fengyuehan at 2011-08-17 16:57:43
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int val[110][110] = {0};
int trace[110][110];
char brackets[110] = {'\0'};

void print(int i, int j){
	if(i > j) return;
	if(i == j){
		if(brackets[i] == '(' || brackets[i] == ')') printf("()");
		else printf("[]");
		return;
	}
	if(trace[i][j] == -1){
		print(i,i);
		print(i+1, j);
		return;
	}
	int k = trace[i][j];
	printf("%c", brackets[i]);
	print(i+1, k-1);
	printf("%c", brackets[k]);
	print(k+1, j);
}

int main() {
	scanf("%s", brackets);
	int len = strlen(brackets);
	for(int i = 0; i < len; i++){
		val[i][i] = 1;
	}
	for(int cha = 1; cha <= len-1; cha ++){
		for(int i = 0; i < len-cha; i++){
			int j = i + cha;
			if(brackets[i] == ')' || brackets[i] == ']') {
				val[i][j] = val[i+1][j] + 1;
				trace[i][j] = -1;
			}
			if(brackets[i] == '('){
				int value = val[i+1][j] + 1;
				int arg = -1;
				for(int k = i+1; k <= j; k++){
					if(brackets[k] != ')') continue;
					int tempval = val[i+1][k-1] + val[k+1][j];
					if(tempval < value){
						arg = k;
						value = tempval;
					}
				}
				val[i][j] = value;
				trace[i][j] = arg;
			}
			if(brackets[i] == '['){
				int value = val[i+1][j] + 1;
				int arg = -1;
				for(int k = i+1; k <= j; k++){
					if(brackets[k] != ']') continue;
					int tempval = val[i+1][k-1] + val[k+1][j];
					if(tempval < value){
						arg = k;
						value = tempval;
					}
				}
				val[i][j] = value;
				trace[i][j] = arg;
			}
		}
	}
	//cout << val[0][len-1] << endl;
	print(0, len-1);
	printf("\n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator