| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一次水过,主要是dp的状态转移,贴代码#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator