2955.txt

来自「用vc自己写的在poj上的题目」· 文本 代码 · 共 45 行

Source

Problem Id:2955  User Id:ygqfq100
Memory:408K  Time:78MS
Language:C++  Result:Accepted

    * Source

      #include<stdio.h>
      #include<string.h>
      #define MAX 300
      #define INF 10000
      int map[MAX][MAX];
      char s[MAX];
      int lns;
      int main()
      {    while(scanf("%s",s) != EOF){
              lns=strlen(s);
      		if(s[0]=='e')
      			break;
      		memset(map,0,sizeof(map));
              for(int k=0;k<lns;k++){
                  for(int j=k,i=0;j<lns;i++,j++) {
                      if(i==j)      
      					map[i][j]=1;
      				else{
                          int min=INF;
                          for(int t=i;t<j;t++){
                              if(min>map[i][t]+map[t+1][j])
                                min=map[i][t]+map[t+1][j];
                          }
                          if(s[i]=='('&&s[j]==')'&&min>map[i+1][j-1])
                              min=map[i+1][j-1];
                          if(s[i]=='[' && s[j] == ']' && min > map[i+1][j-1]) 
                              min=map[i+1][j-1];
                          map[i][j]=min;
                      }
                  }
              }
              printf("%d\n",lns-map[0][lns-1]);     
          }
          return 0;
      }