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

一次水过,主要是dp的状态转移,贴代码

Posted by 1403mashaonan at 2015-02-16 22:46:57 on Problem 1141
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<stack>
using namespace std;
#define MAX 3410
typedef long long LL;
const double pi=3.141592653589793;
const int INF=1e9;
const double inf=1e20;
const double eps=1e-6;
int d[105][105];
char s[105];
bool match(char a,char b){
	if((a=='('&&b==')')||(a=='['&&b==']')) return true;
	return false;
}
void print(int i,int j){
	if(i>j) return;
	if(i==j){
		if(s[i]=='('||s[i]==')') printf("()");
		if(s[i]=='['||s[i]==']') printf("[]");
		return;
	}
	int ans=d[i][j];
	if(ans==d[i+1][j-1]&&match(s[i],s[j])){
		printf("%c",s[i]);
		print(i+1,j-1);
		printf("%c",s[j]);
		return;
	}
	for(int k=i;k<j;k++){
		if(ans==d[i][k]+d[k+1][j]){
			print(i,k);
			print(k+1,j);
			return;
		}
	}
}
int main(){
	scanf("%s",s);
	int n=strlen(s);
	memset(d,0,sizeof(d));
	for(int i=0;i<n;i++) d[i][i]=1;
	for(int l=1;l<n;l++){
		for(int i=0;i<n-l;i++){
			int j=i+l;
			d[i][j]=INF;
			if(match(s[i],s[j])) d[i][j]=d[i+1][j-1];
			for(int k=i;k<j;k++) d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
		}
	}
	print(0,n-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