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