| ||||||||||
| 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