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 |
wa了好几次 假设你的dp正确 wa的原因是要么没有注意空行的输入 要么是保存最终答案的字符串数组开得太小//我的程序是一边dp一边生成答案 没有用递归去输出答案 那我不太会 #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int dp[101][101]; char s[101],ans[101][101][201]; bool check(char c1,char c2) { return((c1=='[' && c2==']')||(c1=='(' && c2==')')); } int main() { int i,j,k,l,n; gets(s); if(strlen(s)) { if(s[strlen(s)-1]==' ') { cout<<endl; return 0; } n=strlen(s)-1; for(i=0;i<=n;i++) { for(j=0;j<=n;j++) dp[i][j]=100000; } for(i=0;i<n;i++) { if(!check(s[i],s[i+1])) { dp[i][i+1]=2; if(s[i]=='[' || s[i]==']') ans[i][i+1][0]='[',ans[i][i+1][1]=']'; else ans[i][i+1][0]='(',ans[i][i+1][1]=')'; if(s[i+1]=='[' || s[i+1]==']') ans[i][i+1][2]='[',ans[i][i+1][3]=']'; else ans[i][i+1][2]='(',ans[i][i+1][3]=')'; ans[i][i+1][4]='\0'; } else dp[i][i+1]=0,ans[i][i+1][0]=s[i],ans[i][i+1][1]=s[i+1],ans[i][i+1][2]='\0'; dp[i][i]=1; if(s[i]=='[' || s[i]==']') ans[i][i][0]='[',ans[i][i][1]=']'; else ans[i][i][0]='(',ans[i][i][1]=')'; ans[i][i][2]='\0'; }; dp[n][n]=1; if(s[n]=='[' || s[n]==']') ans[n][n][0]='[',ans[n][n][1]=']'; else ans[n][n][0]='(',ans[n][n][1]=')'; ans[i][i][2]='\0'; for(l=3;l<=n+1;l++) for(i=0;i<=n-l+1;i++) { j=i+l-1; ans[i][j][0]='\0'; if(check(s[i],s[j])) { dp[i][j]=dp[i+1][j-1]; ans[i][j][0]=s[i]; ans[i][j][1]='\0'; strcat(ans[i][j],ans[i+1][j-1]); k=strlen(ans[i+1][j-1]); ans[i][j][k+1]=s[j]; ans[i][j][k+2]='\0'; } for(k=i;k<j;k++) if(dp[i][j]>dp[i][k]+dp[k+1][j]) { dp[i][j]=dp[i][k]+dp[k+1][j]; strcpy(ans[i][j],ans[i][k]); strcat(ans[i][j],ans[k+1][j]); } } cout<<ans[0][n]<<endl; } else printf("\n"); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator