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 |
这个程序超时,不应该啊。。只是记忆化了一下。。#include <stdio.h> #include <stdlib.h> #include <string.h> char s[101]; int f[101][101]; int max(int a , int b ) { return a>b?a:b; } int Brackets(int l , int r ) { if (f[l][r]>0) return f[l][r]; if ( l == r ) return f[l][r]; int ANS = 0 ; if ((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')) ANS=max(ANS,Brackets(l+1,r-1)+1); if ( s[l]=='('||s[r]==']') ANS=max(ANS,Brackets(l,r-1)); if ( s[r]==')'||s[r]==']') ANS=max(ANS,Brackets(l+1,r)); for ( int k = l ; k < r ; k ++ ) ANS=max(ANS,Brackets(l,k)+Brackets(k+1,r)); f[l][r]=ANS; return ANS; } int main() { while (1) { scanf("%s",&s); if (s[0] == 'e' ) break; int len =strlen(s); int i , j; for ( i = len - 1 ; i >= 0 ; i -- ) s[i+1]=s[i]; for ( i = 1; i <= len ; i ++ ) for ( j = 1; j <= len ; j ++ ) f[i][j]=-1; for ( i = 1; i <= len ; i ++ ) f[i][i] = 0; printf("%d\n",Brackets(1,len)*2); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator