Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这个程序超时,不应该啊。。只是记忆化了一下。。

Posted by ACM06_ghosthy at 2007-12-20 22:36:18 on Problem 2955
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator