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<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=108; char s[maxn]; int dp[maxn][maxn],vis[maxn][maxn]; int max(int x,int y) { if(x>y) return x; return y; } int check(char a,char b) { if(a=='('&&b==')') return 1; if(a=='['&&b==']') return 1; return 0; } void printpost(int i,int j) { if(i>j) return; if(i==j) { if(s[i]==')'||s[i]=='(') printf("()"); else if(s[i]=='['||s[i]==']') printf("[]"); else printf("%c",s[i]); } else { if(vis[i][j]==-1) { printf("%c",s[i]); printpost(i+1,j-1); printf("%c",s[j]); } else { printpost(i,vis[i][j]+i); printpost(vis[i][j]+i+1,j); } } } int main() { int i,j,k; gets(s); memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); int len=strlen(s); if(len==0) { printf("\n"); return 0; } for(i=1;i<len;i++) { if(check(s[i-1],s[i])) { dp[i-1][i]=2; vis[i-1][i]=-1; } } for(k=2;k<len;k++) { for(i=0;i+k<len;i++) { if(check(s[i],s[i+k])) { dp[i][i+k]=dp[i+1][i+k-1]+2; vis[i][i+k]=-1; } for(j=i;j<i+k;j++) { if(dp[i][i+k]<dp[i][j]+dp[j+1][i+k]) { dp[i][i+k]=dp[i][j]+dp[j+1][i+k]; vis[i][i+k]=j-i; } } } } printpost(0,len-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